集合运算

date
Mar 18, 2023
slug
js-set-operation
status
Published
tags
JavaScript数据结构与算法
Set
JavaScript
summary
Set Operation in JavaScript
type
Post

集合运算

并集

​ 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
​ 首先创建一个新的集合，代表两个集合的并集。接下来，获取第一个集合所有的值( values )，迭代并全部添加到代表并集的集合中。将第一个集合中的所有值迭代加入第二个集合中。
union(otherSet){
    const unionSet = new Set();
    
    this.values().forEach( value => {
        unionSet.add(value);
    })
    otherSet.values().forEach( value => {
        unionSet.add(value);
    })
    return unionSet;
}
若不是用 forEach 方法，则使用for循环遍历所有值
union(otherSet){
    const unionSet = new Set();
    
    let values = this.values();
    for(let i = 0; i < values.length; i++){
        unionSet.add(values[i]);
    }
    values = otherSet.values();
    for(let i = 0; i < values.length;i++){
        unionSet.add(values[i]);
    }
    return unionSet;
}
接下来测试并集：
const setA = new Set(); 
setA.add(1); 
setA.add(2); 
setA.add(3); 
const setB = new Set(); 
setB.add(3); 
setB.add(4); 
setB.add(5); 
setB.add(6); 
const unionAB = setA.union(setB); 
console.log(unionAB.values()); 
//[1,2,3,4,5,6]

交集

​ 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
​ 创建一个新的 Set 实例( intersectionSet )，用它返回共有的元素。迭代 当前 Set 实例（集合A）所有的值，验证它们是否也存在于 otherSet 实例（集合B）之中。
has(element){
    return element in items;
}

intersection(otherSet){
    const intersectionSet = new Set();
    
    const values = this.values();
    
    for(let i = 0; i < values.length; i++){
        if(otherSet.has(values[i])){
            intersectionSet.add(values[i]);
        }
    }
    return intersectionSet;
}
测试交集：
const setA = new Set(); 
setA.add(1); 
setA.add(2); 
setA.add(3); 
const setB = new Set(); 
setB.add(2); 
setB.add(3); 
setB.add(4); 
const intersectionAB = setA.intersection(setB); 
console.log(intersectionAB.values()); 
//[2,3]
优化
使用元素少的集合进行迭代比较
intersection(otherSet) { 
 const intersectionSet = new Set(); 
 const values = this.values();  
 const otherValues = otherSet.values();  
 let biggerSet = values;  
 let smallerSet = otherValues;  
 if (otherValues.length - values.length > 0) { 
 biggerSet = otherValues; 
 smallerSet = values; 
 } 
 smallerSet.forEach(value => { 
 if (biggerSet.includes(value)) { 
 intersectionSet.add(value); 
 } 
 }); 
 return intersectionSet; 
}

差集

​ 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集 合的元素的新集合。
​ 创建结果集合，因为不想修改原来的集合。迭代集合中的所有值。检查当前值（元素）是否存在于给定集合中，如果不存在于 otherSet 中，则将此值加入结果集合中。
difference(otherSet){
    const differenceSet = new Set();
    this.values().forEach( value => {
        if(!otherSet.has(value){
           differenceSet.add(value);
           }
    })
    return differenceSet;
}
创建差集测试
const setA = new Set(); 
setA.add(1); 
setA.add(2); 
setA.add(3); 
const setB = new Set(); 
setB.add(2); 
setB.add(3); 
setB.add(4); 
const differenceAB = setA.difference(setB); 
console.log(differenceAB.values());

子集

​ 子集：验证一个给定集合是否是另一集合的子集。
​ 验证的是当前 Set 实例的大小。如果当前实例中的元素比 otherSet 实例更多， 它就不是一个子集。
​ 假定当前实例是给定集合的子集，迭代当前集合的所有元素，验证这些元素也存在于 otherSet 中。如果有任何元素不存在于 otherSet 中， 就意味着它不是一个子集，返回 false。如果所有元素都存在于 otherSet 中，返回 true。
isSubsetOf(otherSet){
    if(this.size() > otherSet.size()){
        return false;
    }
    let isSubset = true;
    this.values().every( value => {
        if(!otherSet.has(value)){
            isSubset = false;
            return false;//使用every，返回false循环停止
        }
        return true;
    })
    return isSubset;
}

© shallrise 2024