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