1. 集合數(shù)據(jù)結(jié)構(gòu)

集合是由一組無序且不重復(fù)的項(xiàng)組成柏副，和數(shù)學(xué)中的有限集合概念一樣，空集就是不包含任何元素的集合。

1.1 創(chuàng)建集合

• add(value)：向集合添加一個(gè)新的項(xiàng)部念。
• delete(value)：從集合中移除一個(gè)值舞痰。
• has(value)：如果值在集合中土榴，返回true，否則返回false响牛。
• clear()：移除集合中的所有項(xiàng)玷禽。
• size()：返回集合所包含元素的數(shù)量。與數(shù)組的length屬性類似呀打。
• values()：返回一個(gè)包含集合中所有值的數(shù)組矢赁。

function Set() {
  let items = {};

  /**
   * 判斷集合中是否存在給定元素
   *
   * @param value
   * @returns {boolean}
   */
  this.has = function (value) {
    return items.hasOwnProperty(value);
  };

  /**
   * 添加新的項(xiàng)
   *
   * @param value
   * @returns {boolean}
   */
  this.add = function (value) {
    if (!this.has(value)) {
      items[value] = value; // 同時(shí)作為鍵和值保存，方便查找
      return true;
    }
    return false;
  };

  /**
   * 移除元素
   *
   * @param value
   * @returns {boolean}
   */
  this.delete = function (value) {
    if (this.has(value)) {
      delete items[value];
      return true;
    }
    return false;
  };

  /**
   * 移除集合中所有項(xiàng)
   */
  this.clear = function () {
    items = {};
  };

  /**
   * 返回集合所包含的元素?cái)?shù)量
   *
   * @returns {number}
   */
  this.size = function () {
    return Object.keys(items).length;
  };

  /**
   * 返回一個(gè)包含集合中所有元素的數(shù)組
   *
   * @returns {[]}
   */
  this.values = function () {
    return Object.keys(items).map(key => items[key]);
  };

  /**
   * 求并集 A∪B
   *
   * @param otherSet
   */
  this.union = function (otherSet) {
    let unionSet = new Set();

    let values = this.values();
    values.forEach(value => unionSet.add(value));

    values = otherSet.values();
    values.forEach(value => unionSet.add(value));

    return unionSet;
  };

  /**
   * 求交集 A∩B
   *
   * @param otherSet
   * @returns {Set}
   */
  this.intersection = function (otherSet) {
    let intersectionSet = new Set();

    let values = this.values();
    values.forEach(value => {
      if (otherSet.has(value)) {
        intersectionSet.add(value);
      }
    });

    return intersectionSet;
  };

  /**
   * 求差集 A-B
   *
   * @param otherSet
   * @returns {Set}
   */
  this.difference = function (otherSet) {
    let differenceSet = new Set();

    let values = this.values();
    values.forEach(value => {
      if (!otherSet.has(value)) {
        differenceSet.add(value);
      }
    });

    return differenceSet;
  };

  /**
   * 判斷A是否是B的子集
   *
   * @param otherSet
   * @returns {boolean}
   */
  this.subset = function (otherSet) {

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

2. 集合相關(guān)問題

2.1 設(shè)計(jì)一個(gè) HashSet

// https://leetcode.com/problems/design-hashset/

// 不使用任何內(nèi)建的哈希表庫贬丛，設(shè)計(jì)一個(gè) HashSet

// add(value): Insert a value into the HashSet.
// contains(value) : Return whether the value exists in the HashSet or not.
// remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

/**
 * Initialize your data structure here.
 */
var MyHashSet = function() {
  this.items = {};
};

/**
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function(key) {
  if (!this.contains(key)) {
    this.items[key] = key;
  }
};

/**
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function(key) {
  if (this.contains(key)) {
    delete this.items[key];
  }
};

/**
 * Returns true if this set contains the specified element
 * @param {number} key
 * @return {boolean}
 */
MyHashSet.prototype.contains = function(key) {
  return this.items.hasOwnProperty(key);
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * var obj = new MyHashSet()
 * obj.add(key)
 * obj.remove(key)
 * var param_3 = obj.contains(key)
 */