90 - 两个数组的交集2

题目

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

示例 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 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解答

根据提示，先不排序再排序

哈希表

作者：zhl1232

链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/js-xie-leetcode-by-zhl1232/

存一下出现的次数

var intersect = function (nums1, nums2) {
  let hash = new Map()
  let res = []
  for (let i = 0; i < nums1.length; i++) {
    if (hash.has(nums1[i])) {
      hash.set(nums1[i], hash.get(nums1[i]) + 1)
    } else {
      hash.set(nums1[i], 1)
    }
  }
  for (let i = 0; i < nums2.length; i++) {
    let temp = nums2[i]
    let hashKey = hash.get(temp)
    if (hash.has(temp)) {
      res.push(temp)
      if (hashKey > 1) {
        hash.set(temp, hashKey - 1)
      } else {
        hash.delete(temp)
      }
    }
  }
  return res
};

Runtime: 52 ms, faster than 95.15% of JavaScript online submissions for Intersection of Two Arrays II.

Memory Usage: 35.7 MB, less than 18.52% of JavaScript online submissions for Intersection of Two Arrays II.

func intersect(nums1 []int, nums2 []int) []int {
    hash := make(map[int]int)
    res := make([]int, 0)
    for _, value := range nums1 {
        if _, ok := hash[value]; ok {
            hash[value]++
        } else {
            hash[value] = 1
        }
    }
    for _, value := range nums2 {
        if val, ok := hash[value]; ok {
            res = append(res, value)
            if val > 1 {
                hash[value]--
            } else {
                delete(hash, value)
            }
        }
    }
    return res
}

Runtime: 4 ms, faster than 84.19% of Go online submissions for Intersection of Two Arrays II.

Memory Usage: 4.8 MB, less than 100.00% of Go online submissions for Intersection of Two Arrays II.

go的哈希表，用起来比js舒服很多

实现这个++功能，js：hash.set(nums1[i], hash.get(nums1[i]) + 1)，go：hash[value]++

明显go舒服很多

还有检查有没有这个数go: if val, ok := hash[value]; ok {...}

js还要调用一个方法hash.has(nums1[i])

还是觉得go的处理一劳永逸，且优雅

双指针

var intersect = function (nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)
  const result = []
  for (let i = 0, j = 0; i < nums1.length && j < nums2.length;) {
    if (nums1[i] === nums2[j]) {
      result.push(nums1[i])
      i++
      j++
    } else if (nums1[i] < nums2[j]) {
      i++
    } else {
      j++
    }
  }
  return result
};

Runtime: 68 ms, faster than 31.20% of JavaScript online submissions for Intersection of Two Arrays II.

Memory Usage: 35.1 MB, less than 66.67% of JavaScript online submissions for Intersection of Two Arrays II.

双指针反而慢了😂

func intersect(nums1 []int, nums2 []int) []int {
    sort.Ints(nums1)
    sort.Ints(nums2)
    result := make([]int, 0)
    for i, j := 0, 0; i < len(nums1) && j < len(nums2); {
        if nums1[i] == nums2[j] {
            result = append(result, nums1[i])
            i++
            j++
        } else if nums1[i] < nums2[j] {
            i++
        } else {
            j++
        }
    }
    return result
}

Runtime: 4 ms, faster than 84.19% of Go online submissions for Intersection of Two Arrays II.

Memory Usage: 4.5 MB, less than 100.00% of Go online submissions for Intersection of Two Arrays II.