title

给定两个数组, 编写一个函数来计算它们的交集。

示例 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 的数据结构来统计次数。

1. 将 num1、nums2 各自出现的次数分别统计存进 nums1Map 与 nums2Map 中;
2. 根据题目说明中的条件可以不考虑输出结果的顺序, 因而可以以 num1、nums2 相同的 key 中较小的值为输出次数, 将其输出;

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  const nums1Map = getMap(nums1)
  const nums2Map = getMap(nums2)

  const result = []

  nums1Map.forEach((nums1Value, key) => {
    const nums2MapHasKey = nums2Map.get(key)
    if (nums2MapHasKey) {
      for (let i = 0; i < Math.min(nums1Value, nums2MapHasKey); i++) {
        result.push(key)
      }
    }
  })

  return result
};

var getMap = function(arr) {
  const map = new Map()
  for (let i = 0; i < arr.length; i++) {
    const getValue = map.get(arr[i])
    if (!getValue) {
      map.set(arr[i], 1)
    } else {
      map.set(arr[i], getValue + 1)
    }
  }
  return map
}

进阶

如果给定的两个数组是排好序的, 是否有其它解法呢?

相关题

202、205、242、290、349、451