内容
给定两个数组,写一个方法来计算它们的交集。
例如:
给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].
注意:
输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
跟进:
如果给定的数组已经排好序呢?你将如何优化你的算法?
如果 nums1 的大小比 nums2 小很多,哪种方法更优?
如果nums2的元素存储在磁盘上,内存是有限的,你不能一次加载所有的元素到内存中,你该怎么办?
思路
一看到是找交集,那么就有循环循环循环查找,为了避免这个过程,采用hash表的方式是最快的查找方式,所以将较大的数组的所有元素放入map中,
再遍历较小的数组,如果map中该元素的出现次数大于0,那么就记录一次
代码
/**
一看到是找交集,那么就有循环循环循环查找,为了避免这个过程,采用hash表的方式是最快的查找方式,所以将较大的数组的所有元素放入map中,
再遍历较小的数组,如果map中该元素的出现次数大于0,那么就记录一次
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function (nums1, nums2) {
var map = {};
var maxNum;
var minNum = nums1.length < nums2.length ? (maxNum = nums2, nums1) : (maxNum = nums1, nums2);
for (var value of maxNum) {
map[value] ? map[value]++ : map[value] = 1;
}
var result = [];
for (var value of minNum) {
if (map[value]) {
result.push(value);
map[value]--;
}
}
return result;
};