仙居网站建设/凡科建站平台

话不多说，先看题目：

给定两个数组，编写一个函数来计算它们的交集。

示例 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]  9            i++
10        } else {
11            nums1[k] = nums1[i]
12            i++
13            j++
14            k++
15        }
16    }
17    return nums1[:k]
18}

提示：解答中我们并没有创建空白数组，因为遍历后的数组其实就没用了。我们可以将相等的元素放入用过的数组中，就为我们节省下了空间。

温馨提示

如果觉得有帮助的话，动动小指头关注哈~同时点下右下方的在看也可以支持浩仔~

浩仔讲算法，每天一起学习图解漫画算法。一起刷题，一起成长。

有任何问题和建议都可以下方留言哦~