Open
Description
350.两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
进阶:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
思路
为两个数组分别建立 map，用来存储 num -> count 的键值对，统计每个数字出现的数量。
然后对其中一个 map 进行遍历，查看这个数字在两个数组中分别出现的数量，取出现的最小的那个数量（比如数组 1 中出现了 1 次，数组 2 中出现了 2 次，那么交集应该取 1 次），push 到结果数组中即可。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
let intersect = function (nums1, nums2) {
let map1 = makeCountMap(nums1)
let map2 = makeCountMap(nums2)
let res = []
for (let num of map1.keys()) {
const count1 = map1.get(num)
const count2 = map2.get(num)
if (count2) {
const pushCount = Math.min(count1, count2)
for (let i = 0; i < pushCount; i++) {
res.push(num)
}
}
}
return res
}
function makeCountMap(nums) {
let map = new Map()
for (let i = 0; i < nums.length; i++) {
let num = nums[i]
let count = map.get(num)
if (count) {
map.set(num, count + 1)
} else {
map.set(num, 1)
}
}
return map
}进阶
-
排好序的数组。
对于排好序的数组，用双指针的方法会更优。 -
两个数组数量差距很大。
优先遍历容量小的数组，提前结束循环。