j
jaryue
V1
2023/03/26阅读:13主题:默认主题
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
哈希表
-
建立一个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
双指针+排序
-
先对2个数组进行排序
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指针后移
}
}
执行结果
法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

作者介绍
j
jaryue
V1