Title

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]

示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]

說明：

輸出結果中每個元素出現的次數，應與元素在兩個數組中出現的次數一致。
我們可以不考慮輸出結果的順序。

排序

Solve

如果兩個數組是有序的，則可以便捷地計算兩個數組的交集。

首先對兩個數組進行排序，然后使用兩個指針遍歷兩個數組。

初始時，兩個指針分別指向兩個數組的頭部。每次比較兩個指針指向的兩個數組中的數字，如果兩個數字不相等，則將指向較小數字的指針右移一位，如果兩個數字相等，將該數字添加到答案，并將兩個指針都右移一位。當至少有一個指針超出數組范圍時，遍歷結束。

Code

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:nums1.sort()nums2.sort()i, j, length1, length2, ans = 0, 0, len(nums1), len(nums2), []while i < length1 and j < length2:if nums1[i] == nums2[j]:ans.append(nums1[i])i += 1j += 1elif nums1[i] < nums2[j]:i += 1else:j += 1return ans

復雜度分析

時間復雜度：O(mlogm+nlogn)，其中 m 和 n 分別是兩個數組的長度。對兩個數組進行排序的時間復雜度是 O(mlogm+nlogn)，遍歷兩個數組的時間復雜度是 O(m+n)，因此總時間復雜度是 O(mlogm+nlogn)。

空間復雜度：O(min(m,n))，其中 m 和 n 分別是兩個數組的長度。

總結

以上是生活随笔為你收集整理的350. Intersection of Two Arrays II 两个数组的交集 II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。