JS数据结构与算法入门(五) - 数据结构之“集合”

本是古典何须时尚 2022-12-02 13:50 189阅读 0赞

## 1. 集合是什么? ##

一种无序且唯一的数据结构  
集合要求它的元素必须唯一, 不可重复  
ES6中有集合, 叫Set  
**集合的常用操作:**

> 去重, 判断某元素是否在集合中, 求交集

代码演示:

// 去重
    const arr = [1,1,2,2];
    //const arr2 = new Set(arr);
    // 实例化一个set对象, 传入arr, 
    // 会得到一个1和2组成的集合, 但是最终想要的是一个数组
    // 所以需要把集合转化为数组 [...new Set(arr)]
    const arr2 = [...new Set(arr)]

// 判断元素是否在集合中
    const arr = [1,1,2,2];
    
    const set = new Set(arr);
    //set中有has方法可直接判断
    const has = set.has(1) //true

// 求交集
    const arr = [1,1,2,2];
    
    const set2 = new Set([2,3]);
    //1.先把set转换为数组
    //2.用filter方法筛选出set2里面也有的值
    //3.最终得到的数组用new Set方法把它实例化成新的集合, 这样就得到一个交集
    const set3 = new Set([...set].filter(item => set2.has(item)));

**试题**  
力扣349  
给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
输出：\[2\]  
示例 2：

输入：nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\]  
输出：\[9,4\]

要求: 求交集无序且唯一

解题思路:

1.  用集合对 nums1 去重
2.  遍历去重后的nums1, 筛选出nums2也包含的值

var intersection = function(nums1,nums2) { 
      //把数组nums1放到set里面, 用...把set赋值到一个数组里
      //新数组就是去重后的nums1, 然后遍历nums1, 并从中筛选出nums2也包含的值
      //new Set(nums2).has 用set把nums2变成集合, 用set的has方法判断nums2里面是否包含值
      return [...new Set(nums1)].filter( n => new Set(nums2).has(n));
    }
    
    //优化
    var intersection = function(nums1,nums2) { 
      return [...new Set(nums1)].filter( n => nums2.includes(n));
    }
    
    // 时间复杂度: 看filter循环 O(n)的2次方
    // 空间复杂度: O(m)

## 2. 使用ES6的Set ##

set操作:

1.  使用set对象: new, add, delete, has, size

> new Set 实例化一个对象, 然后使用其中的方法

1.  迭代Set: 多种迭代方法, set和Array如何互转, 求交集/差集

> for(let item of set.keys())  
> console.log(item)

//set转array
    
    // 方法一:
    const myArr = [...set]
    
    // 方法二:
    const myArr = Array.from(set)
    -------------------------------------------
    //array转set
    
    const myset = new Set([1,2,3,4])

求交集
    const intersection = new Set([...myset].filter(x => myset2.has(x)))
    
    求差集
    const difference = new Set([...myset].filter(x => !myset2.has(x)))