爱囡囡，爱前端

0%

TypeScript数据结构与算法：集合

发表于 分类于 ， ，

上一篇《TypeScript 数据结构与算法：链表》实现了 Typescript 中链表的数据结构与算法，本篇继续实现集合。

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

集合（Set）之间的运算包括并集、交集、差集等，如下图所示：

数据结构

集合

一个集合中，应该有以下方法：

  • add(element)：向集合添加一个新元素。
  • delete(element)：从集合移除一个元素。
  • has(element)：如果元素在集合中，返回 true，否则返回 false。
  • clear()：移除集合中的所有元素。
  • size()：返回集合所包含元素的数量。它与数组的 length 属性类似。
  • values()：返回一个包含集合中所有值（元素）的数组。
  • union(otherSet)：返回与其他集合的并集。
  • intersection(otherSet)：返回与其他集合的交集。
  • difference(otherSet)：返回与其他集合的差集。
  • isSubsetOf(otherSet)：返回是否为其他集合的子集。

在 ES2015 后，已经存在原生的 Set 数据结构了，但是没有上面所述的所有方法，所以以原生 Set 为基础来构造一个 CustomSet：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
export default class CustomSet<T> {
  private items: Set<T>;

  constructor(array?: T[]) {
    this.items = new Set(array);
  }

  /**
   * @description: 向集合添加一个新元素。
   * @param {T} element
   * @return {boolean} 是否添加成功
   */
  add(element: T): boolean {
    if (!this.has(element)) {
      this.items.add(element);
      return true;
    }
    return false;
  }

  /**
   * @description: 从集合移除一个元素。
   * @param {T} element
   * @return {boolean} 是否删除成功
   */
  delete(element: T): boolean {
    if (this.has(element)) {
      return this.items.delete(element);
    }
    return false;
  }

  /**
   * @description: 如果元素在集合中，返回 true，否则返回 false。
   * @param {T} element
   * @return {boolean}
   */
  has(element: T): boolean {
    return this.items.has(element);
  }

  /**
   * @description: 返回一个包含集合中所有值（元素）的数组。
   * @return {Array<T>}
   */
  values(): T[] {
    return [...this.items];
  }

  /**
   * @description: 并集
   * @param {CustomSet} otherSet
   * @return {CustomSet}
   */
  union(otherSet: CustomSet<T>): CustomSet<T> {
    const unionSet = new CustomSet<T>();

    // 迭代两个集合，把元素都add进来
    this.values().forEach((value) => unionSet.add(value));
    otherSet.values().forEach((value) => unionSet.add(value));

    return unionSet;
  }

  /**
   * @description: 交集
   * @param {CustomSet} otherSet
   * @return {CustomSet}
   */
  intersection(otherSet: CustomSet<T>): CustomSet<T> {
    const intersectionSet = new CustomSet<T>();

    // 在当前集合中过滤掉otherSet中不存在的元素
    this.values()
      .filter((v) => otherSet.has(v))
      .forEach((v) => {
        intersectionSet.add(v);
      });

    return intersectionSet;
  }

  /**
   * @description: 差集
   * @param {CustomSet} otherSet
   * @return {CustomSet}
   */
  difference(otherSet: CustomSet<T>): CustomSet<T> {
    const differenceSet = new CustomSet<T>();

    // 在当前集合中过滤掉otherSet中也存在的元素
    this.values()
      .filter((v) => !otherSet.has(v))
      .forEach((v) => {
        differenceSet.add(v);
      });

    return differenceSet;
  }

  /**
   * @description: 是否为子集
   * @param {CustomSet} otherSet
   * @return {boolean}
   */
  isSubsetOf(otherSet: CustomSet<T>): boolean {
    if (this.size() > otherSet.size()) {
      return false;
    }

    let isSubset = true;
    // 判据：当前集合的所有元素在otherSet中都存在
    this.values().forEach((value) => {
      if (!otherSet.has(value)) {
        isSubset = false;
      }
    });

    return isSubset;
  }

  /**
   * @description: 是否为空
   * @return {boolean}
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 集合的元素数
   * @return {number}
   */
  size(): number {
    return this.items.size;
  }

  /**
   * @description: 清空集合
   */
  clear() {
    this.items = new Set();
  }

  /**
   * @description: 替换原生toString
   * @return {string}
   */
  toString(): string {
    return `${this.values()}`;
  }
}

多重集

集合数据结构不允许存在重复的元素。但是，在数学中有一个叫作 多重集 的概念，允许我们向集合中插入重复元素。多重集（MultiSet）在计算集合中元素的出现次数时很有用。

多重集有一些方法和普通集合有区别：

  • count(element)：返回集合中指定元素的数目。
  • set(element, count)：将集合中指定元素设为 count 个。
  • add(element, count)：向集合添加 count 个指定元素。
  • remove(element, count)：在集合删除 count 个指定元素。
  • delete(element)：从集合移除所有指定元素。
  • dimension()：返回集合所包含元素的种类数。它与数组的 length 属性类似。

具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
export default class MultiSet<T> {
  private items: Map<T, number>;

  constructor() {
    this.items = new Map();
  }

  /**
   * @description: 如果元素在集合中，返回 true，否则返回 false。
   * @param {T} element
   * @return {boolean}
   */
  has(element: T): boolean {
    return this.items.has(element);
  }

  /**
   * @description: 返回元素的维数，也就是元素的种类数
   * @return {number}
   */
  dimension(): number {
    return this.items.size;
  }

  /**
   * @description: 返回该元素的个数
   * @param {T} element
   * @return {number}
   */
  count(element: T): number {
    return this.items.get(element) ?? 0;
  }

  /**
   * @description: 删除所有的该元素
   * @param {T} element
   * @return {boolean}
   */
  delete(element: T): boolean {
    return this.items.delete(element);
  }

  /**
   * @description: 设置该元素的个数
   * @param {T} element
   * @param {number} count
   * @return {boolean}
   */
  set(element: T, count: number): boolean {
    if (count <= 0) {
      return this.delete(element);
    }
    this.items.set(element, count);
    return true;
  }

  /**
   * @description: 给该元素添加count个
   * @param {T} element
   * @param {number} count
   * @return {boolean}
   */
  add(element: T, count: number = 1): boolean {
    let newCount = this.count(element) + count;
    return this.set(element, newCount);
  }

  /**
   * @description: 给该元素移除count个
   * @param {T} element
   * @param {number} count
   * @return {boolean}
   */
  remove(element: T, count: number = 1): boolean {
    return this.add(element, -count);
  }

  /**
   * @description: 是否为空
   * @return {boolean}
   */
  isEmpty(): boolean {
    return this.dimension() === 0;
  }

  // 👇 以下方法与CustomSet的同名方法实现一致

  /**
   * @description: 返回一个包含集合中所有值（元素）的数组。
   * @return {Array<T>}
   */
  values(): T[] {
    return Array.from(this.items.entries()).reduce((acc, cur) => {
      const [key, value] = cur;
      for (let i = 0; i < value; i++) {
        acc.push(key);
      }
      return acc;
    }, []);
  }

  /**
   * @description: 集合的元素数
   * @return {number}
   */
  size(): number {
    return this.values().length;
  }

  /**
   * @description: 清空集合
   */
  clear() {
    this.items = new Map();
  }

  /**
   * @description: 并集
   * @param {MultiSet} otherSet
   * @return {MultiSet}
   */
  union(otherSet: MultiSet<T>): MultiSet<T> {
    const unionSet = new MultiSet<T>();

    // 迭代两个集合，把元素都add进来
    this.values().forEach((value) => unionSet.add(value));
    otherSet.values().forEach((value) => unionSet.add(value));

    return unionSet;
  }

  /**
   * @description: 交集
   * @param {MultiSet} otherSet
   * @return {MultiSet}
   */
  intersection(otherSet: MultiSet<T>): MultiSet<T> {
    const intersectionSet = new MultiSet<T>();

    // 在当前集合中过滤掉otherSet中不存在的元素
    this.values()
      .filter((v) => otherSet.has(v))
      .forEach((v) => {
        intersectionSet.add(v);
      });

    return intersectionSet;
  }

  /**
   * @description: 差集
   * @param {MultiSet} otherSet
   * @return {MultiSet}
   */
  difference(otherSet: MultiSet<T>): MultiSet<T> {
    const differenceSet = new MultiSet<T>();

    // 在当前集合中过滤掉otherSet中也存在的元素
    this.values()
      .filter((v) => !otherSet.has(v))
      .forEach((v) => {
        differenceSet.add(v);
      });

    return differenceSet;
  }

  /**
   * @description: 是否为子集
   * @param {MultiSet} otherSet
   * @return {boolean}
   */
  isSubsetOf(otherSet: MultiSet<T>): boolean {
    if (this.size() > otherSet.size()) {
      return false;
    }

    let isSubset = true;
    // 判据：当前集合的所有元素在otherSet中都存在
    this.values().forEach((value) => {
      if (!otherSet.has(value)) {
        isSubset = false;
      }
    });

    return isSubset;
  }

  /**
   * @description: 替换原生toString
   * @return {string}
   */
  toString(): string {
    return `${this.values()}`;
  }
}

下一篇来分析字典。

前端记事本，不定期更新，欢迎关注！

👆 全文结束，棒槌时间到 👇