https://leetcode-cn.com/problems/intersection-of-two-arrays-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 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
题目分析
这道题比较简单,我们来分析下。题目中给出说明不考虑输出结果的顺序,则可以联想到使用对象来保存数组中出现的数字。题目中还要求输出每个元素出现的次数,可以联想到使用对象的值来保存元素出现的次数。
下面使用 JS 代码实现:
const intersect = function(nums1 = [], nums2 = []) {
const numsMap1 = {}
nums1.forEach((num) => {
if (numsMap1[num] === void 0) {
numsMap1[num] = 0
}
numsMap1[num] += 1
})
const intersection = []
nums2.forEach((num) => {
if (numsMap1[num] > 0) {
intersection.push(num)
numsMap1[num] -= 1
}
})
return intersection
}
时间复杂度:
空间复杂度:
除了上面使用对象的方法来做,还可以对这两个数组先进行排序,然后再使用两个指针遍历数组,当碰到相同的元素时,push 到新数组中。
下面使用 JS 代码实现:
const intersect = function(nums1 = [], nums2 = []) {
const nums1Order = nums1.sort((a, b) => a - b)
const nums2Order = nums2.sort((a, b) => a - b)
let index1 = 0
let index2 = 0
const intersection = []
while(index1 < nums1Order.length && index2 < nums2Order.length) {
if (nums1Order[index1] === nums2Order[index2]) {
intersection.push(nums1Order[index1])
index1 ++
index2 ++
} else if (nums2Order[index2] < nums1Order[index1]) {
index2 ++
} else if (nums2Order[index2] > nums1Order[index1]) {
index1 ++
}
}
return intersection
}
时间复杂度:
空间复杂度: