1. 集合数据结构

集合是由一组无序且不重复的项组成，和数学中的有限集合概念一样，空集就是不包含任何元素的集合。

1.1 创建集合

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

  • values()：返回一个包含集合中所有值的数组。

    1. function Set() {
    2. let items = {};
    4. /**
    5.  * 判断集合中是否存在给定元素
    6.  *
    7.  * @param value
    8.  * @returns {boolean}
    9.  */
    10. this.has = function (value) {
    11.   return items.hasOwnProperty(value);
    12. };
    14. /**
    15.  * 添加新的项
    16.  *
    17.  * @param value
    18.  * @returns {boolean}
    19.  */
    20. this.add = function (value) {
    21.   if (!this.has(value)) {
    22.     items[value] = value; // 同时作为键和值保存，方便查找
    23.     return true;
    24.   }
    25.   return false;
    26. };
    28. /**
    29.  * 移除元素
    30.  *
    31.  * @param value
    32.  * @returns {boolean}
    33.  */
    34. this.delete = function (value) {
    35.   if (this.has(value)) {
    36.     delete items[value];
    37.     return true;
    38.   }
    39.   return false;
    40. };
    42. /**
    43.  * 移除集合中所有项
    44.  */
    45. this.clear = function () {
    46.   items = {};
    47. };
    49. /**
    50.  * 返回集合所包含的元素数量
    51.  *
    52.  * @returns {number}
    53.  */
    54. this.size = function () {
    55.   return Object.keys(items).length;
    56. };
    58. /**
    59.  * 返回一个包含集合中所有元素的数组
    60.  *
    61.  * @returns {[]}
    62.  */
    63. this.values = function () {
    64.   return Object.keys(items).map(key => items[key]);
    65. };
    67. /**
    68.  * 求并集 A∪B
    69.  *
    70.  * @param otherSet
    71.  */
    72. this.union = function (otherSet) {
    73.   let unionSet = new Set();
    75.   let values = this.values();
    76.   values.forEach(value => unionSet.add(value));
    78.   values = otherSet.values();
    79.   values.forEach(value => unionSet.add(value));
    81.   return unionSet;
    82. };
    84. /**
    85.  * 求交集 A∩B
    86.  *
    87.  * @param otherSet
    88.  * @returns {Set}
    89.  */
    90. this.intersection = function (otherSet) {
    91.   let intersectionSet = new Set();
    93.   let values = this.values();
    94.   values.forEach(value => {
    95.     if (otherSet.has(value)) {
    96.       intersectionSet.add(value);
    97.     }
    98.   });
    100.   return intersectionSet;
    101. };
    103. /**
    104.  * 求差集 A-B
    105.  *
    106.  * @param otherSet
    107.  * @returns {Set}
    108.  */
    109. this.difference = function (otherSet) {
    110.   let differenceSet = new Set();
    112.   let values = this.values();
    113.   values.forEach(value => {
    114.     if (!otherSet.has(value)) {
    115.       differenceSet.add(value);
    116.     }
    117.   });
    119.   return differenceSet;
    120. };
    122. /**
    123.  * 判断A是否是B的子集
    124.  *
    125.  * @param otherSet
    126.  * @returns {boolean}
    127.  */
    128. this.subset = function (otherSet) {
    130.   if (this.size() > otherSet.size()) {
    131.     return false;
    132.   } else {
    133.     let values = this.values();
    134.     for (let i = 0; i < values.length; i++) {
    135.       if (!otherSet.has(values[i])) {
    136.         return false;
    137.       }
    138.     }
    139.     return true;
    140.   }
    141. };
    142. }

    2. 集合相关问题

    2.1 设计一个 HashSet

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

// 不使用任何内建的哈希表库，设计一个 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) */ ```