leetcode350重复数据

leecode

题目描述

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2] 示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]

提示：

1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/intersection-of-two-arrays-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

哈希表

1. 建立一个map[int]int,(第一个int储存在表中出现的数据,第二个储存出现的次数)

m := make(map[int]int)//第一个int储存在表中出现的数据,第二个储存出现的次数
//遍历n1我们使用加法,n2遍历使用减法,保证m的value>0;

循环遍历

for i := 0; i < len(nums1); i++ {//遍历n1中存在的元素,储存在map中
  m[nums1[i]] = m[nums1[i]] + 1
 }
 i := 0
 for j := 0; j < len(nums2); j++ {//遍历索引m中n2为key的value是否>0//是就可以输出此数据
  if m[nums2[j]] > 0 {
   nums1[i] = nums2[j]
   m[nums2[j]]--
   i++
  }
 }

法2

双指针+排序

1. 先对2个数组进行排序

sort.Ints(nums1) //排序;;i索引
 sort.Ints(nums2) //排序;;j索引

2. 循环遍历数组并且对比找出相同的值

//k用于赋值
   k := 0
   for i, j := 0, 0; i < len(nums1) && j < len(nums2); {//当ij同时在范围内时执行,有一个超出范围就退出
    if nums1[i] == nums2[j] {//相同时
     nums1[k] = nums1[i]//赋值,指针后移
     i++
     j++
     k++
    } else if nums1[i] > nums2[j] {
     j++//n1i>n1j时j指针后移
    } else {
     i++//n1i<n1j时i指针后移
    }
   }

执行结果

法1

func intersect(nums1 []int, nums2 []int) []int {
 m := make(map[int]int)
 for i := 0; i < len(nums1); i++ {//遍历n1中存在的元素,储存在map中
  m[nums1[i]] = m[nums1[i]] + 1
 }
 i := 0
 for j := 0; j < len(nums2); j++ {//遍历索引m中n2为key的value是否>0//是就可以输出此数据
  if m[nums2[j]] > 0 {
   nums1[i] = nums2[j]
   m[nums2[j]]--
   i++
  }
 }
 return nums1[:i]//返回需要的数据
}

执行用时： 4 ms , 在所有 Go 提交中击败了 72.71% 的用户 内存消耗： 2.9 MB , 在所有 Go 提交中击败了 60.32% 的用户 通过测试用例： 56 / 56

方法2

// II 排序+双指针
func intersect(nums1 []int, nums2 []int) []int {
 sort.Ints(nums1) //排序;;i索引
 sort.Ints(nums2) //排序;;j索引
 //k用于赋值
 k := 0
 for i, j := 0, 0; i < len(nums1) && j < len(nums2); {//当ij同时在范围内时执行,有一个超出范围就退出
  if nums1[i] == nums2[j] {//相同时
   nums1[k] = nums1[i]//赋值,指针后移
   i++
   j++
   k++
  } else if nums1[i] > nums2[j] {
   j++//n1i>n1j时j指针后移
  } else {
   i++//n1i<n1j时i指针后移
  }
 }
 return nums1[:k]//返回范围值
}

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2.6 MB , 在所有 Go 提交中击败了 100.00% 的用户 通过测试用例： 56 / 56