两个数组的交集?如果两个数组是有序的呢?
共 1285字,需浏览 3分钟
·
2020-03-04 23:24
来源:小浩算法
作者:程序员浩哥
话不多说,先看题目:
第350题:给定两个数组,编写一个函数来计算它们的交集。给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明:
输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
进阶:
如果给定的数组已经排好序呢?你将如何优化你的算法?
设定两个为0的指针,比较两个指针的元素是否相等。如果指针的元素相等,我们将两个指针一起向前移动,并且将相等的元素放入空白数组。
首先拿到这道题,我们基本马上可以想到此题可以看成是一道传统的映射题(map映射),为什么可以这样看呢,因为我们需找出两个数组的交集元素,同时应与两个数组中出现的次数一致。这样就导致了我们需要知道每个值出现的次数,所以映射关系就成了<元素,出现次数>。剩下的就是顺利成章的解题。
由于该种解法过于简单,我们不做进一步分析,直接给出题解:
1func intersect1(nums1 []int, nums2 []int) []int {
2 m0 := map[int]int{}
3 for _, v := range nums1 {
4 //遍历nums1,初始化map
5 m0[v] += 1
6 }
7 k := 0
8 for _, v := range nums2 {
9 //如果元素相同,将其存入nums2中,并将出现次数减1
10 if m0[v] > 0 {
11 m0[v] -= 1
12 nums2[k] = v
13 k++
14 }
15 }
16 return nums2[0:k]
17}
相信大家都能看懂!
题目在进阶问题中问道:如果给定的数组已经排好序呢?你将如何优化你的算法?我们分析一下,假如两个数组都是有序的,分别为:arr1 = [1,2,3,4,4,13],arr2 = [1,2,3,9,10]
两个排序好数组的题,我们很容易可以想到通过双指针的解法~
<1>设定两个为0的指针,比较两个指针的元素是否相等。如果指针的元素相等,我们将两个指针一起向前移动,并且将相等的元素放入空白数组。
<2>如果两个指针的元素不相等,我们将小的一个指针前移。
<3>反复以上步骤。
<4>直到任意一个数组终止。
根据分析,我们很容易得到下面的题解:
1func intersect(nums1 []int, nums2 []int) []int {
2 i, j, k := 0, 0, 0
3 sort.Ints(nums1)
4 sort.Ints(nums2)
5 for i < len(nums1) && j < len(nums2) {
6 if nums1[i] > nums2[j] {
7 j++
8 } else if nums1[i] < nums2[j] {
9 i++
10 } else {
11 nums1[k] = nums1[i]
12 i++
13 j++
14 k++
15 }
16 }
17 return nums1[:k]
18}
提示:解答中我们并没有创建空白数组,因为遍历后的数组其实就没用了。我们可以将相等的元素放入用过的数组中,就为我们节省下了空间。
推荐阅读