数据结构之集合

本篇文章可以收获的知识：

• 什么是集合
• 集合的使用场景
• 一道LeetCode算法题巩固集合
• 如何分析时间复杂度和空间复杂度
• JavaScript中的集合

什么是集合

集合是一种无序且唯一的数据结构，ES6中的集合，名为Set

集合的使用场景

• 数组去重

  const a1 = [1, 1, 2, 2, 3, 4, 5];
  const a2 = [...new Set(a1)]
  

• 判断元素是否存在集合中

  const s = new Set([1, 2, 3, 4])
  s.has(1) // 返回boolean
  

• 求两个集合的交集

  const s1 = new Set([1, 2, 3, 4])
  const s2 = new Set([2, 3])
  const s3 = new Set([...s1].filter(i => s1.has(i)))
  

LeetCode算法题：题号349，两个数组的交集

解题思路：

• 求交集且唯一
• 使用集合

解题步骤：

• 使用集合对数组进行去重
• 遍历其中一个数据，判断另一个数据是否包含

实现代码：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
  const s1 = new Set(nums1);
  const s2 = new Set(nums2);
  const res = [...s1].filter(i => s2.has(i))
  return res
};

因为代码有用到了filter，每一个元素都要进行过滤，循环次数最大可能是nums1的长度乘以nums2的长度，所以时间复杂度是O(n * m)，n是nums1的长度，m是nums2的长度。

因为代码中用到了set数据结构，长度最大是两个数组中最大的长度，所以空间复杂度是O(n)，n是数组的长度。

这道LeetCode的算法题的最优解法是使用字典数据结构解决，在数据结构之字典文章中也会提及。

JavaScript中的集合

// JavaScript中集合的常用操作
const s = new Set()
s.add(1) // 添加操作
s.delete(1) // 删除操作
s.size() // 获取集合的长度
s.has(1) // 判断集合中是否有当前元素

// JavaScript中集合的迭代
for(let item of m) {}
for(let item of m.keys()) {}
for(let item of m.values()) {}
for(let [key, value] of m.entries()) {} // key === value

// JavaScript中集合与数组互转
const a = Array.from(new Set([1, 2]))
const s1 = new Set(a)

最后，希望读者可以通过本篇文章对集合有一定的认识和觉悟。。。。。。