两个数组的交集 II-350

[sl1673495]

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
}

进阶

1. 排好序的数组。 对于排好序的数组，用双指针的方法会更优。

2. 两个数组数量差距很大。 优先遍历容量小的数组，提前结束循环。

[zzy-cl]

let intersect = function (nums1, nums2) {
    let arr1 = [], arr2 = []

    if (nums1.length !== nums2.length) {
        arr1 = nums1.length < nums2.length ? nums1 : nums2
        arr2 = nums1.length > nums2.length ? nums1 : nums2
    } else {
        arr1 = nums1
        arr2 = nums2
    }
    let res = []
    for (let i = 0; i < arr1.length; i++) {
        let a = arr2.indexOf(arr1[i])
        if (a !== -1) {
            res.push(arr1[i])
            arr2.splice(a, 1)
        }
    }
    return res
};