数据结构与算法之集合: Leetcode 349. 两个数组的交集 (Typescript版)

两个数组的交集

• https://leetcode.cn/problems/intersection-of-two-arrays/description/

描述

• 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1

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

示例 2

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

算法实现

1 ）使用数组filter+集合的has方法

function intersection (nums1: number[], nums2: number[]): number[] {return [...new Set(nums1)].filter(n => new Set(nums2).has(n)); // 这里filter内部函数每次都会new Set, 不合适
}

• 这个算法的问题是代码书写逻辑重复，或者说因编码经验而导致的性能低下

2 ）使用数组filter+集合的has方法 优化版

function intersection (nums1: number[], nums2: number[]): number[] {const n2 = new Set(nums2);return [...new Set(nums1)].filter(n => n2.has(n));
}

• 只需要一次set, 无需循环中每次都做

3 ）使用数组filter+数组includes方法或indexOf方法

function intersection (nums1: number[], nums2: number[]): number[] {return [...new Set(nums1)].filter(n => nums2.includes(n)); // 或 indexOf 来处理: nums2.indexOf(n) > -1
}

4 ）排序 + 双指针

function intersection (nums1: number[], nums2: number[]): number[] {nums1.sort((x, y) => x - y);nums2.sort((x, y) => x - y);const length1 = nums1.length, length2 = nums2.length;let index1 = 0, index2 = 0;const intersection = [];while (index1 < length1 && index2 < length2) {const num1 = nums1[index1], num2 = nums2[index2];if (num1 === num2) {// 保证加入元素的唯一性if (!intersection.length || num1 !== intersection[intersection.length - 1]) {intersection.push(num1);}index1++;index2++;} else if (num1 < num2) {index1++;} else {index2++;}}return intersection;
}

• 这种是官方示例，代码实现比较复杂，主要依靠两个数组的同一规则排序
• 之后使用两个指针来指向当前元素，当两者相同时，如果唯一，则存储
• 在实际应用中，虽然效率上还行，但是并不推荐上述算法实践，代码冗余
  • 时间复杂度主要在两个sort排序, nlogn + mlogm
  • 空间复杂度也是在两个sort排序，logn + logm

TS中的集合扩展

1 ）Set操作，使用Set对象：new、add、delete、has、size

let mySet = new set();
mySet.add(1);
mySet.add(5);
mySet.add(5); // 不会保留多个5，只会保留1个
mySet.add('ssse');
let o = {name: 1};
mySet.add(o);
mySet.add({name:1}); // 会保留两个对象，它们内存地址是不同的console.log(mySet.has(1)); // true
console.log(mySet.has(3)); // false
console.log(mySet.has(5)); // true
console.log(mySet.has('ssse')); // true
console.log(mySet.has(o)); // truemySet.delete(5);

2 ）迭代Set

// 迭代1 for of 迭代
for(let item of mySet) console.log(item);
// 迭代2
for(let item of mySet.keys()) console.log(item);
// 迭代3
for(let item of mySet.values()) console.log(item); // 值同key
// 以上三种迭代, 输出结果一致// 下面通过entries()方法来调用
for(let [key, value] of mySet.entries()) console.log(key, value); // 打印key和value果然完全一样

3 ）Set 和 Array互转

// Set转Array, 方式1
const myArr = [...mySet];
// Set转Array, 方式2
const myArr = Array.from(mySet);
// Array转Set
const mySet2 = new Set([1,2,3,4])

4 ）Set的交集和差集

// 求两个Set交集
const intersection = new Set([...mySet].filter(x => mySet2.has(x)))// 求两个Set差集
const difference = new Set([...mySet].filter(x => !mySet2.has(x)))