leetcode349两个数组的交集

leecode

题目描述

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

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

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的

提示：

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

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

解题思路

法1

哈希表\

1. 建立一个map索引[int]int

m := make(map[int]int)//第一个储存值第二个储存,减值大于0

2. 存数,向map中储存n1中出现的数
3. 查数,查找n2中在n1中出现的数字并储存在n1中

for i := 0; i < len(nums1); i++ {//记录i出现过的数值
  if m[nums1[i]] == 0 {
   m[nums1[i]] = 1
  }
 }
 i := 0
 for j := 0; j < len(nums2); j++ {//查找n2中在n1中出现的数字并储存在n1中以免申请新的空间
  if m[nums2[j]] > 0 {
   m[nums2[j]] = 0
   nums1[i] = nums2[j]
   i++
  }
 }
 return nums1[:i]//返回需要的数组切片

执行结果

法1

func intersection(nums1 []int, nums2 []int) []int {
 m := make(map[int]int)
 for i := 0; i < len(nums1); i++ {//记录i出现过的数值
  if m[nums1[i]] == 0 {
   m[nums1[i]] = 1
  }
 }
 i := 0
 for j := 0; j < len(nums2); j++ {//查找n2中在n1中出现的数字并储存在n1中以免申请新的空间
  if m[nums2[j]] > 0 {
   m[nums2[j]] = 0
   nums1[i] = nums2[j]
   i++
  }
 }
 return nums1[:i]//返回需要的数组切片
}

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

优化方案

1. value改成bool类型
2. 删除已经出现过的节点释放空间,而不是令其=false

func intersection1(nums1 []int, nums2 []int) []int {
 m := make(map[int]bool)//value改成bool类型
 for i := 0; i < len(nums1); i++ {
  if !m[nums1[i]] {
   m[nums1[i]] = true
  }
 }
 i := 0
 for j := 0; j < len(nums2); j++ {
  if m[nums2[j]] {
   delete(m, nums2[j])//删除已经出现过的节点释放空间,而不是令其=false
   nums1[i] = nums2[j]
   i++
  }
 }
 return nums1[:i]
}

执行结果： 通过 显示详情 查看示例代码 添加备注

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

法3