coolliyong.github.io

集合

《学习 JavaScript 数据结构与算法》中集合的解释：

集合是由一组无序且唯一（即不能重复）的项组成的。这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。

在深入学习集合的计算机科学实现之前，我们先看看它的数学概念。在数学中，集合是一组不同的对象（的集）。

比如说，一个由大于或等于 0 的整数组成的自然数集合：N = {0, 1, 2, 3, 4, 5, 6, …}。集合中的对象列表用“{}”（大括号）包围。

还有一个概念叫空集。空集就是不包含任何元素的集合。比如 24 和 29 之间的素数集合。由于 24 和 29 之间没有素数（除了 1 和自身，没有其他正因数的大于 1 的自然数），这个集合就是空集。空集用“{ }”表示。

你也可以把集合想象成一个既没有重复元素，也没有顺序概念的数组。
在数学中，集合也有并集、交集、差集等基本操作。在这一章中我们也会介绍这些操作。

封装集合

ES6（ES2015 中）已经实现了Set类，但是为了更好理解，可以先手动封装一个Set类

首先需要确定 Set 可操作性的方法

add(value)：向集合添加一个新的项。
delete(value)：从集合移除一个值。
has(value)：如果值在集合中，返回 true，否则返回 false。
clear()：移除集合中的所有项。
size()：返回集合所包含元素的数量。与数组的 length 属性类似。
values()：返回一个包含集合中所有值的数组。

具体实现

function Set() {
  this.item = {}
}
Set.prototype.add = function(data) {
  this.item[data] = data
}
Set.prototype.clear = function() {
  this.item = {}
}
Set.prototype.has = function(value) {
  return this.item.hasOwnProperty(value)
}
Set.prototype.delete = function(value) {
  if (this.has(value)) {
    delete this.item[value]
    return true
  }
  return false
}

Set.prototype.size = function() {
  return Object.keys(this.item).length
}

Set.prototype.values = function() {
  return Object.keys(this.item)
}

集合操作

并集
交集
差集
子集

代码实现

// 并集
Set.prototype.union = function(otherSet) {
  const _set = new Set()
  otherSet.values().forEach(v => {
    _set.add(v)
  })
  this.values().forEach(v => {
    _set.add(v)
  })
  return _set
}

// 交集
Set.prototype.intersection = function(otherSet) {
  const _set = new Set()
  otherSet.values().forEach(v => {
    if (this.has(v)) {
      _set.add(v)
    }
  })
  return _set
}

// 差集
Set.prototype.difference = function(otherSet) {
  const _set = new Set()
  otherSet.values().forEach(v => {
    if (!this.has(v)) {
      _set.add(v)
    }
  })
  this.values().forEach(v => {
    if (!otherSet.has(v)) {
      _set.add(v)
    }
  })
  return _set
}

// 子集 当前集合是否是otherSet 的子集
Set.prototype.subset = function(otherSet) {
  if (this.size() > otherSet.size()) {
    return false
  }

  const values = this.values()
  for (let i = 0; i < values.length; i++) {
    if (!otherSet.has(values[i])) {
      return false
    }
  }
  return true
}

ES6 - `Set` 类

ES6 提供了新的数据结构 Set。它类似于数组，但是成员的值都是唯一的，没有重复的值。

const set = new Set([1, 2, 3, 4, 4])
[...set]
// [1, 2, 3, 4]

// 例二
const items = new Set([1, 2, 3, 4, 5, 5, 5, 5])
items.size // 5

// 例三
const set = new Set(document.querySelectorAll('div'))
set.size // 56

数组去重

[...new Set(arr)]

向 Set 加入值的时候，不会发生类型转换，所以5和”5”是两个不同的值。Set 内部判断两个值是否不同，使用的算法叫做“Same-value-zero equality”，它类似于精确相等运算符（===），主要的区别是向 Set 加入值时认为NaN等于自身，而精确相等运算符认为NaN不等于自身。

let set = new Set();
let a = NaN;
let b = NaN;
set.add(a);
set.add(b);
set // Set {NaN}