数据结构-集合

集合定义

基本操作

// 去重
const arr = [1, 1, 2, 2];
const set = new Set(arr);  // 将数组放入集合中即可去重
console.log(set);      // {size: 2, 1, 2}
console.log(...set);   // 将集合进行解构得到 1 2
const arr2 = [...set]; // 将结构出来的数存在数组中
console.log(arr2);      // [1, 2]
console.log('******************************************************');

// 判断元素是否在集合中
const set0 = new Set([1, 3, 2, 4]);
const has = set0.has(2);  // 判断2 是否在集合中
console.log(has);
console.log('******************************************************');

//求交集
const set1 = new Set([1, 1, 2, 2]);   // 实例化一个集合
const set2 = new Set([2, 3]);
// 调用 filter() 过滤器方法 
const set3 = new Set([...set1].filter( item => {return set2.has(item)} ));
console.log([...set3]);

刷题

LeetCode: 349.两个数组的交集

题目描述

解题思路

解题步骤

Code

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    // 方法一
    // let set1 = new Set(nums1);
    // let set2 = new Set(nums2);
    // let set3 = new Set([...set1].filter(item => set2.has(item)));
    // let arr = [...set3];
    // return arr;

    // 方法二   相当于上述代码的简化版
    // return [...new Set(nums1)].filter(n => new Set(nums2).has(n));
    // 方法三 优化 判断元素是否在数组中没必要使用集合的方法,使用数组的includes()方法即可
    return [...new Set(nums1)].filter(n => nums2.includes(n));

};

时间复杂度 空间复杂度分析

• 因其中调用了filter(),且里面包含了includes() ，所以时间复杂度为O(n^2)
• 因去重后的数存储在数组[]中，所以空间复杂度为O(n)

前端与集合：使用ES6的Set

Set操作

let mySet = new Set();

// *************************************************************
// 添加元素
mySet.add(1);
mySet.add(5);   //  因为集合有唯一性 所以，只添加了一个5
mySet.add(5);
mySet.add('hello');
let o = {a: 1, b: 2};
mySet.add(o);
mySet.add({ a: 1, b: 2 }); // 此时两个对象看似一样但在内存中的存储空间完全不一样，所以集合中有两个对象。

// *************************************************************
// has方法 判断 是否在集合中
const has = mySet.has(1);

// *************************************************************
// 删除元素
mySet.delete(5);

// *************************************************************
// 迭代

// 方法1
for(let item of mySet) console.log(item);
console.log('*******');

// 方法2   keys()
for(let item of mySet.keys()) console.log(item);
console.log('*******');

// 方法3   values()
for(let item of mySet.values()) console.log(item);
console.log('*******');

// 方法4   entries() 可同时调用keys,和values  
for(let [keys, values] of mySet.entries()) console.log(keys, values);

// *************************************************************
// 集合和数组互转

// 集合转数组
// 方法1
const myArr = [...mySet];

// 方法2
const myAr2 = Array.from(mySet);


// 数组转集合
const mySet2 = new Set([1, 2 ,3, 4]);

// *************************************************************
// 求交集和差集

// 求交集
const intersection = new Set([...mySet].filter(n => mySet2.has(n)));

// 求差集
const difference = new Set([...mySet].filter(n => !mySet2.has(n)));

总结