JS数据结构和算法 - 集合

什么是集合？

集合是由一组无序且唯一的元素组成（集合中没有重复项 - 集合中的元素使用===来判断是否相同）

实现一个集合

function Set() {
    let items = {};
}

注意一个细节，我们使用一个对象而不是数组来表示集合。原因：JS中对象不能有相同的key，可以用来保证集合的元素具有唯一性

需要实现的方法

• add(value)

• remove(value)

• has(value)

• clear()

• size()

• values()

function Set() {
  let items = {};
  this.has = function (value) {
    return items.hasOwnProperty(value);
  }

  this.add = function (value) {
    if (!this.has(value)) {
      items[value] = value;
      return true;
    }
    return false;
  }

  this.remove = function (value) {
    if (this.has(value)) {
      delete items[value];
      return true;
    }
    return false;
  }

  this.clear = function () {
    items = {};
  }

  this.size = function () {
    return Object.keys(items).length;
  }

  this.values = function () {
    return Object.keys(items);
  }

  this.union = function (otherSet) {
    const set = new Set();
    const values = this.values();
    const otherValues = otherSet.values();
    for (let i = 0; i < values.length; i++) {
      set.add(values[i]);
    }
    for (let i = 0; i < otherValues.length; i++) {
      set.add(otherValues[i])
    }
    return set;
  }

  this.intersection = function (otherSet) {
    const set = new Set();
    const values = this.values();
    for (let i = 0; i < values.length; i++) {
      if (otherSet.has(values[i])) {
        set.add(values[i]);
      }
    }
    return set;
  }

  this.difference = function (otherSet) {
    const set = new Set();
    const values = this.values();
    for (let i = 0; i < values.length; i++) {
      if (!otherSet.has(values[i])) {
        set.add(values[i])
      }
    }
    return set;
  }
  // 判断当前集合是不是otherSet的子集
  this.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;
  }
}

集合的操作

• 并集

• 交集

• 差集

• 子集