【 数据集合】并集、交集、差集、子集

• 集合是由一组无序且唯一的项组成。你可以把集合想象成一个既没有重复元素，也没有顺序概念的数组。还有一个概念叫空集。空集就是不包括任何元素的集合。空集用{}表示。

创建集合类

• ECMAScript2015介绍了Set类是Javascript API的一部分，我们将基于ES2015的Set类来实现我们自己的Set类。我们也会实现一些原生ES2015没有提供的集合运算，例如并集、交集和差集。

class Set {
    constructor() {
        this.items = {};
    }
}
复制代码

• 我们使用对象而不是数组来表示集合（items）的原因有两个：
  • 第一个是因为在使用数组时，大部分方法的时间复杂度是O(n)。即我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置。如果数组有更多元素的话，所需的时间会更长。另外，数组是元素的一个有序集合。为了保证元素排列有序，它会占用更多的内存空间。
  • 另一个就是因为Javascript的对象不允许一个键指向两个不同属性，也保证了集合里的元素都是唯一的。

老规矩-来搞几个Set类的方法

1. has() 检验某个元素是否存在于集合中

has(element) {
    return Object.prototype.hasOwnProperty.call(this.items, element); // 返回一个表明对象是否具有特定属性的布尔值
  }
复制代码

• Object原型有hasOwnProperty方法。该方法返回一个表明对象是否具有特定属性的布尔值。
• 也可以使用this.items.hasOwnProperty(element),但这样的话代码检查 工具 如(ESLint)会抛出一个错误。错误的原因为不是所有的对象都继承了Object.prototype,甚至继承的Object,prototype的对象上的hasOwnProperty方法也有可能会被覆盖，导致代码不能正常工作。
• element in items也可以。in运算符返回表示对象在原型链上是否有特定属性的布尔值。

2. add() 向集合添加一个新元素

add(element) {
    if (!this.has(element)) { // 检查
      this.items[element] = element; // 如果不存在，就把element添加到集合中，返回true {element:element}
      return true;
    }
    return false; //  如果集合中有相同的元素，返回false即可
  }
复制代码

• 添加一个元素的时候，把它同时作为键和值保存，因为这样有利于查找该元素

3. delete（）从集合中删除一个元素

delete(element) {
    if (this.has(element)) { // 检查，只能删除存在与集合中的，（集合中都没有，你删谁去~）
      delete this.items[element]; // 从集合中移除element
      return true; // 返回true
    }
    return false; // 如果集合中没有，返回false
  }
复制代码

• 既然我们用对象来存储集合的items对象，就可以简单的使用delete运算符从items对象中移除属性。

4. size()返回集合中有多少元素

size() { // 返回集合中有多少元素
    return Object.keys(this.items).length; // 使用原生的内置方法，把对象的key转化为数组，再返回其length
  }
复制代码

5. values()返回一个包含集合中所有所有值的数组

values() { // 返回一个包含集合中所有所有值的数组
    return Object.values(this.items); // 同样使用原生方法（它是在ECMAscript2017中被添加进来的，目前只在现在浏览器中可用）
  }
复制代码

• 现在就实现了一个和ECMASscript2015中非常类似的Set类实现。

集合运算

• 我们可以对集合进行如下运算：
  • 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
  • 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
  • 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
  • 子集：验证一个给定集合是否是另一个集合的子集。

1.并集

• 该集合的定义是：x（元素）存在于A中，或x存在于B中。实现代码如下：

union(otherSet) {
    const unionSet = new Set(); // 创建一个新的集合
    this.values().forEach(value => unionSet.add(value)); // 获取第一个集合（当前的set类实例）所有的值并添加到新集合中
    otherSet.values().forEach(value => unionSet.add(value)); // 获取第二个集合（传入的set类实例）所有的值并添加到新集合中
    return unionSet; // 最后返回创建的新集合
  }
复制代码

2.交集

• 由所有属于集合A且属于集合B的元素所组成的集合，叫做集合A与集合B的交集。实现代码如下：

intersection(otherSet) {
    const intersectionSet = new Set(); // 创建一个新的集合
    const values = this.values(); // 获取第一个集合（当前的set类实例）
    const otherValues = otherSet.values(); // 获取第二个集合（传入的set类实例）
    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; // 返回新集合
  }
复制代码

• 首先创建一个新的集合来存放intersection方法返回的结果。
• 然后要获取当前集合实例中的值和传入集合中的值。
• 先假设当前集合的元素较多， 传入集合的元素较少。
• 再比较两个集合的元素个数，如果另一个集合的元素个数比当前集合的元素个数多的话，就交换较多的等于传入的，较少的等于当前集合。
• 迭代较少集合，如果两个集合中都有当前元素，把它插入到新集合当中
• 最后返回新集合
• 对两个集合的元素个数做比较的目的是为了尽量最少循环迭代，更少的迭代次数意味这更少的过程消耗。

3. 差集

（没找到更好的图片，自己也懒的画了，意思大家表达清除就好 哈~~）

• 元素存在A中，且x不存在于B中。实现代码如下：

difference(otherSet) {
    const differenceSet = new Set(); // 创建一个新的集合
    this.values().forEach(value => { // 当前集合的值转换为数组，并循环
      if (!otherSet.has(value)) { // 如果传入的集合中没有这个元素
        differenceSet.add(value); // 把它添加到新集合中
      }
    });
    return differenceSet; // 返回新的集合
  }
复制代码

4. 子集

• 集合A的每一个元素，也需要存在于集合B中。实现代码如下：

isSubsetOf(otherSet) {
    if (this.size() > otherSet.size()) { // 如果当前集合的元素比传入集合多，那它肯定不是传入集合的子集，返回false
      return false;
    }
    let isSubset = true; // 先假设当前集合是传入集合的子集
    // 迭代当前集合,当发现一个返回false,便不再执行。
    this.values().every(value => {
      if (!otherSet.has(value)) { // 验证迭代的元素是否也存在传入集合中
        isSubset = false; // 只要有一个不是就改变变量
        return false; // 返回false 不再往下执行
      }
      return true; // 如果都是，返回true
    });
    return isSubset; // 最后返回变量isSubset
  }
复制代码

• 首先要验证当前集的元素比传入集的小，如果当前集合的元素比传入集合还多，那它肯定不是传入集合的子集，返回false
• 然后先假设当前集合是传入集合的子集。
• 迭代当前集合的所有元素，验证这些元素也存在于传入集合中。
• 如果有任何元素不存在于传入集合中，就意味着它不是一个子集，返回false。
• 如果所有元素都存在于传入集合中，就返回true，isSubset变量不会改变。
• 在子集方法中我们用的是every方法。当我们发现一个值不存在于传入集合时，可以停止迭代值，表示这不是一个子集。

ECMAScript2015——Set类

• 先来看看原生的set类怎么用：

const set = new Set();
set.add(1);
console.log(set.values()); // 输出@Iterator
console.log(set.has(1)); // 输出true
console.log(set.values()); // 输出1
复制代码

• ES2015的set的values方法返回Iterator（一个包含键值对的迭代器对象），而不是值构成的数组。
• 另一个区别是，我们实现的size方法返回set中存储的值的个数，而ES2015的 Set则有一个size属性。
• 我们实现的set类实现了并集、交集、差集、子集这些数学运算，然而ES6原生的Set并没有这些功能。

ES6Set运算模拟

• 首先创建两个集合，等会儿会用到

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);
复制代码

1. 模拟并集运算

const union = (set1, set2) => { // 普通模拟
  const unionAb = new Set();
  set1.forEach(value => unionAb.add(value));
  set2.forEach(value => unionAb.add(value));
  return unionAb;
};
console.log(union(setA, setB)); // [1,2,3,4]

console.log(new Set([...setA, ...setB]));  // 使用 扩展运算符模拟 [1,2,3,4]
复制代码

2. 模拟交集运算

const intersection = (set1, set2) => { // 普通模拟， 未经优化的
  const intersectionSet = new Set();
  set1.forEach(value => {
    if (set2.has(value)) {
      intersectionSet.add(value);
    }
  });
  return intersectionSet;
};
console.log(intersection(setA, setB)); // [2,3]

console.log(new Set([...setA].filter(x => setB.has(x)))); // 使用 扩展运算符模拟 [2,3]
复制代码

3. 模拟差集运算

const difference = (set1, set2) => { // 普通模拟
  const differenceSet = new Set();
  set1.forEach(value => {
    if (!set2.has(value)) {
      differenceSet.add(value);
    }
  });
  return differenceSet;
};
console.log(difference(setA, setB));// [1]

console.log(new Set([...setA].filter(x => !setB.has(x)))); // 使用 扩展运算符模拟 [1]
复制代码

最后

好了，今天的随手笔记完事儿了。本文内容全来自本人阅读过《学习Javascript数据结构与算法》第七章后稍加整理而成。