350. 两个数组的交集 II

和上题一致，但是不去重，重复数字可以有多个

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？
  • 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
  • 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2] ，而不是【2】

结语

如果 _nums_2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中。那么就无法高效地对 _nums_2 进行排序，因此不推荐使用方法二双指针法。
在方法一哈希法中，_nums_2 只关系到查询操作，因此每次读取 _nums_2 中的一部分数据，并进行处理即可。

复杂度分析

  • 时间复杂度：O(m+n)，其中 mm 和 nn 分别是两个数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。

  • 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 res，其长度为较短的数组的长度。

    1. //哈希键判断。
    2. //把较小的数组转成哈希表,再遍历较大的数组查找交集
    3. func intersect(nums1 []int, nums2 []int ) []int {
    4.   if len(nums1) > len(nums2) {            //1,遍历较小的数组进哈希表，优化空间
    5.       return intersect(nums2, nums1)
    6.   }
    8.   hash_m := map[int]int{}                 //2,定义哈希数组，哈希的数量多少 == 哈希键
    9.   res := []int{}
    11.   for _, num := range nums1 {
    12.       hash_m[num]++                            //3,哈希键，记录重复次数，v->k类型 不是键值类型
    13.   }
    15.   for _, num := range nums2 {
    16.       if hash_m[num] >0 {                      //4,当遍历第二个数组时，遇到重复值，加入res
    17.           res = append(res, num)
    18.           hash_m[num]--                        //5,哈希键，重复数量-1，直到重复数超过，上一个数组存的
    19.       }
    20.   }
    21.   return res
    22. }

复杂度分析

  • 时间复杂度：O(m_log_m+n_log_n)，其中 m 和 n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是O(m_log_m+n_log_n)，遍历两个数组的时间复杂度是 O(m+n)，因此总时间复杂度是O(m_log_m+n_log_n)。

  • 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。为返回值创建一个数组 res，其长度为较短的数组的长度。

    //排序+双指针
func intersection(nums1 []int, nums2 []int) []int {
  sort.Ints(nums1)
  sort.Ints(nums2)

  res := make([]int, len(nums1))
  pre1, pre2, index := 0, 0, 0

  for pre1 < len(nums1) && pre2 < len(nums2) {
      if nums1[pre1] < nums2[pre2] {
          pre1++                                            //数值小的，指针向后一位
      }else if nums1[pre1] > nums2[pre2] {
          pre2++
      //}else if index  > 0 && nums1[pre1] == res[index-1] {        //若有两个相同，回溯一位
      //    pre1++
      //    pre2++

      } else{
          res[index] = nums1[pre1]                        //记录重复值，存储res数组
          index++
          pre1++
          pre2++
      }
  }
  return res[0: index]
}