兩個數組的交集？如果兩個數組是有序的呢？

• 2020 年 3 月 5 日
• 筆記

來源：小浩演算法

作者：程式設計師浩哥

01

題目分析

話不多說，先看題目：

第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映射），為什麼可以這樣看呢，因為我們需找出兩個數組的交集元素，同時應與兩個數組中出現的次數一致。這樣就導致了我們需要知道每個值出現的次數，所以映射關係就成了<元素,出現次數>。剩下的就是順利成章的解題。

由於該種解法過於簡單，我們不做進一步分析，直接給出題解：

func intersect1(nums1 []int, nums2 []int) []int {      m0 := map[int]int{}      for _, v := range nums1 {          //遍歷nums1，初始化map          m0[v] += 1      }      k := 0      for _, v := range nums2 {          //如果元素相同，將其存入nums2中，並將出現次數減1          if m0[v] > 0 {              m0[v] -= 1              nums2[k] = v              k++          }      }      return nums2[0:k]  }  

相信大家都能看懂！

02

題目進階

題目在進階問題中問道：如果給定的數組已經排好序呢？你將如何優化你的演算法？我們分析一下，假如兩個數組都是有序的，分別為：arr1 = [1,2,3,4,4,13]，arr2 = [1,2,3,9,10]

兩個排序好數組的題，我們很容易可以想到通過雙指針的解法~

<1>設定兩個為0的指針，比較兩個指針的元素是否相等。如果指針的元素相等，我們將兩個指針一起向前移動，並且將相等的元素放入空白數組。

<2>如果兩個指針的元素不相等，我們將小的一個指針前移。

<3>反覆以上步驟。

<4>直到任意一個數組終止。

根據分析，我們很容易得到下面的題解：

03

題目解答

func intersect(nums1 []int, nums2 []int) []int {      i, j, k := 0, 0, 0      sort.Ints(nums1)      sort.Ints(nums2)      for i < len(nums1) && j < len(nums2) {          if nums1[i] > nums2[j] {              j++          } else if nums1[i] < nums2[j] {              i++          } else {              nums1[k] = nums1[i]              i++              j++              k++          }      }      return nums1[:k]  }  

提示：解答中我們並沒有創建空白數組，因為遍歷後的數組其實就沒用了。我們可以將相等的元素放入用過的數組中，就為我們節省下了空間。