LeetCode 350. 两个数组的交集 II
题目描述
思路分析
解法一：哈希表
解法二：排序+双指针
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func intersect(nums1 []int, nums2 []int) []int {
// 创建哈希表存储 nums1 中元素的频率
count := make(map[int]int)
for _, num := range nums1 {
count[num]++
}
// 遍历 nums2，找交集并记录
var res []int
for _, num := range nums2 {
if count[num] > 0 {
res = append(res, num)
count[num]-- // 计数减一，避免重复计入
}
}
return res
}
- 时间复杂度：O(m + n)，其中 m 是
nums1的长度，n 是nums2的长度。我们需要遍历nums1和nums2各一次。- 空间复杂度：O(min(m, n))，哈希表的大小与
nums1中元素的不同个数相关。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func intersect(nums1 []int, nums2 []int) []int {
// 先对两个数组进行排序
sort.Ints(nums1)
sort.Ints(nums2)
var res []int
i, j := 0, 0
// 使用双指针查找交集
for i < len(nums1) && j < len(nums2) {
if nums1[i] == nums2[j] {
res = append(res, nums1[i])
i++
j++
} else if nums1[i] < nums2[j] {
i++
} else {
j++
}
}
return res
}
时间复杂度：O(m log m + n log n)，其中 m 是
nums1的长度，n 是nums2的长度。排序操作的时间复杂度为 O(m log m) 和 O(n log n)，然后双指针遍历两个数组的时间复杂度为 O(m + n)。
空间复杂度：O(1)，只使用了常数级的空间。
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！