两个数组的交集
- https://leetcode.cn/problems/intersection-of-two-arrays/description/
题目和解题参考
- https://blog.csdn.net/Tyro_java/article/details/133279737
使用字典来解题的算法实现
字典:顾名思义,像新华字典一样可查找,基于键值对来存储
function intersection (nums1: number[], nums2: number[]): number[] {const map = new Map();nums1.forEach(n => {map.set(n, true);});let res = [];nums2.forEach(n => {// 匹配if(map.get(n)) {res.push(n);map.delete(n); // 紧接着移除改字典,因为已经用过了 }});return res;
}
- 上述算法时间复杂度 O(n)
- 准确来说是 O(m+n)
- 空间复杂度O(n)
- 注意:空间复杂度是临时变量的内存消耗,这里 map 是线性增长的,res也可能是线性增长的,所以最大就是 O(n)
TS中字典Map常用的api回顾
const m = new Map();// 增、改
m.set('a', 1); // 增加
m.set('b', true); // 增加
m.set('a', 2); // 修改// 查
m.get('a');// 删
m.delete('a');
m.clear();