两个数组的交集?如果两个数组是有序的呢?

苦逼的码农

共 1285字,需浏览 3分钟

 ·

2020-03-04 23:24

来源:小浩算法

作者:程序员浩哥


01题目分析


话不多说,先看题目:

d5af24c9c9a29fab1edad175df062928.webp第350题:给定两个数组,编写一个函数来计算它们的交集。0fca560f710cb3c8548cf70f5b7c5cda.webp

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


示例 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的指针,比较两个指针的元素是否相等。如果指针的元素相等,我们将两个指针一起向前移动,并且将相等的元素放入空白数组。


13dd95f95238134541aad270e2fa5296.webp

首先拿到这道题,我们基本马上可以想到此题可以看成是一道传统的映射题(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}


相信大家都能看懂!


02题目进阶


c7df4d44bd8d8fcb6baf59e2788a369d.webp

题目在进阶问题中问道:如果给定的数组已经排好序呢?你将如何优化你的算法?我们分析一下,假如两个数组都是有序的,分别为:arr1 = [1,2,3,4,4,13],arr2 = [1,2,3,9,10]


698ae6343d524062ad538d8f50b58f21.webp


两个排序好数组的题,我们很容易可以想到通过双指针的解法~

<1>设定两个为0的指针,比较两个指针的元素是否相等。如果指针的元素相等,我们将两个指针一起向前移动,并且将相等的元素放入空白数组。

be3acab6ef013f1667ae4bf4443095b5.webp

<2>如果两个指针的元素不相等,我们将小的一个指针前移。

f79fa0b40e56ccfa4510a71353b26018.webp

<3>反复以上步骤。

88a876613292573d5fec8e6f2a7416f7.webp

<4>直到任意一个数组终止。

8c6a36f3565e63c702c5488013b69b73.webp


根据分析,我们很容易得到下面的题解:


03题目解答


 1func intersect(nums1 []int, nums2 []int) []int {
2    i, j, k := 000
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}


13dd95f95238134541aad270e2fa5296.webp

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


推荐阅读

全部文章分类与整理(算法+数据结构+计算机基础),持续更新

【吐血整理】那些让你起飞的计算机基础知识:学什么,怎么学?

普普通通,我的三年大学

写公众号15个月以来,这一路上的学习与收获

历经两个月,我的秋招之路结束了!

2020 第一篇原创 | 我是如何让自己变的更加优秀的?

浏览 17
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报