兩個(gè)數(shù)組的交集?如果兩個(gè)數(shù)組是有序的呢?
來(lái)源：小浩算法
作者：程序員浩哥
話(huà)不多說(shuō)，先看題目：
第350題：給定兩個(gè)數(shù)組，編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算它們的交集。
給定兩個(gè)數(shù)組，編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算它們的交集。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說(shuō)明：
輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致。
我們可以不考慮輸出結(jié)果的順序。
進(jìn)階:
如果給定的數(shù)組已經(jīng)排好序呢？你將如何優(yōu)化你的算法？
設(shè)定兩個(gè)為0的指針，比較兩個(gè)指針的元素是否相等。如果指針的元素相等，我們將兩個(gè)指針一起向前移動(dòng)，并且將相等的元素放入空白數(shù)組。
首先拿到這道題，我們基本馬上可以想到此題可以看成是一道傳統(tǒng)的映射題（map映射），為什么可以這樣看呢，因?yàn)?strong>我們需找出兩個(gè)數(shù)組的交集元素，同時(shí)應(yīng)與兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致。這樣就導(dǎo)致了我們需要知道每個(gè)值出現(xiàn)的次數(shù)，所以映射關(guān)系就成了<元素,出現(xiàn)次數(shù)>。剩下的就是順利成章的解題。
由于該種解法過(guò)于簡(jiǎn)單，我們不做進(jìn)一步分析，直接給出題解：
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中，并將出現(xiàn)次數(shù)減1
10????????if?m0[v]?>?0?{
11????????????m0[v]?-=?1
12????????????nums2[k]?=?v
13????????????k++
14????????}
15????}
16????return?nums2[0:k]
17}
相信大家都能看懂！
題目在進(jìn)階問(wèn)題中問(wèn)道：如果給定的數(shù)組已經(jīng)排好序呢？你將如何優(yōu)化你的算法？我們分析一下，假如兩個(gè)數(shù)組都是有序的，分別為：arr1 = [1,2,3,4,4,13]，arr2 = [1,2,3,9,10]
兩個(gè)排序好數(shù)組的題，我們很容易可以想到通過(guò)雙指針的解法~
<1>設(shè)定兩個(gè)為0的指針，比較兩個(gè)指針的元素是否相等。如果指針的元素相等，我們將兩個(gè)指針一起向前移動(dòng)，并且將相等的元素放入空白數(shù)組。
<2>如果兩個(gè)指針的元素不相等，我們將小的一個(gè)指針前移。
<3>反復(fù)以上步驟。
<4>直到任意一個(gè)數(shù)組終止。
根據(jù)分析，我們很容易得到下面的題解：
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}
提示：解答中我們并沒(méi)有創(chuàng)建空白數(shù)組，因?yàn)楸闅v后的數(shù)組其實(shí)就沒(méi)用了。我們可以將相等的元素放入用過(guò)的數(shù)組中，就為我們節(jié)省下了空間。
推薦閱讀
全部文章分類(lèi)與整理（算法+數(shù)據(jù)結(jié)構(gòu)+計(jì)算機(jī)基礎(chǔ)），持續(xù)更新
【吐血整理】那些讓你起飛的計(jì)算機(jī)基礎(chǔ)知識(shí)：學(xué)什么，怎么學(xué)？
寫(xiě)公眾號(hào)15個(gè)月以來(lái)，這一路上的學(xué)習(xí)與收獲