用Python（Java）分别：求兩個數組的交集

題目:

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

示例 1:

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

示例 2:

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

說明:

輸出結果中每個元素出現的次數,應與元素在兩個數組中出現的次數一緻。

我們可以不考慮輸出結果的順序。

進階:

如果給定的數組已經排好序呢?你将如何優化你的算法?

如果 nums1 的大小比 nums2 小很多,哪種方法更優?

如果 nums2 的元素存儲在磁盤上,磁盤記憶體是有限的,并且你不能一次加載所有的元素到記憶體中,你該怎麼辦?

用Python（Java）分别：求兩個數組的交集

解題思路:

暴力解題就不說了。

哈希表:利用哈希映射求得其中一個數組每個數字出現的頻次。周遊另一個數組,每遇到相同數字,其存儲頻次減一,若頻次為 0,則移出哈希映射。如:

輸入 nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4 }計算 nums1 頻次: { 4:1, 9:1, 5:1 },Key = {4 , 9, 5 }周遊 nums2:9 存在于 Key,9 頻次 -1 為 0,9 移出 HashMap:{ 4:1, 5:1 }4 存在于 Key,4 頻次 -1 為 0,4 移出 HashMap:{ 5:1 }9 不存在于 Key,跳過8 不存在于 Key,跳過...輸出:{9, 4}
雙指針:先把兩個數組排序,定義兩個指針 i, j ,移動指針
如果 nums1 [i] == nums2 [j],則該數共有。
           

如果不等,則移動元素值小的指針。

如：

輸入 nums1 = [ 4, 9, 5 ], nums2 = [ 9, 4, 9, 8, 4 ]
排序 nums1 = [ 4, 5, 9 ], nums2 = [ 4, 4, 8, 9, 9 ]
雙指針周遊：[ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^
 4 = 4, 存入 res = [4], 移動雙指針: [ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^
5 > 4, 移動指向 4 的指針:[ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^
5 < 8, 移動指向 5 的指針:[ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^

9 > 8, 移動指向 8 的指針:[ 4, 5, 9]，[ 4, 4, 8, 9, 9 ]
 ^ ^

9 = 9, 存入 res = [4, 9], 移動雙指針: [ 4, 5, 9 ]，[ 4, 4, 8, 9, 9 ]
 ^ ^
超過 nums1 長度，結束，傳回 res
           

回答進階問題:

雙指針法主要耗時操作就是排序操作的排序算法。對于有序數組當然使用雙指針解題。

在一個數組長度遠小于另一個數組時,哈希表解題更優,隻需哈希統計長度較小的數組的元素頻次,周遊長數組即可。時間複雜度取決于長數組長度。如果用雙指針法,對長數組的排序将消耗更多時間。

如果記憶體有限,隻能選擇雙指針法或暴力破解,無需額外空間複雜度。使用哈希表時在最壞情況下:每個數字隻出現一次,HashMap 元素頻次統計後,其大小可能大于記憶體容量。

哈希表解題:

Java:

class Solution {
 public int[] intersect(int[] nums1, int[] nums2) {
 HashMap<Integer, Integer> map = new HashMap<>();
 List<Integer> list = new ArrayList<>();//動态數組
 for (Integer num : nums1) map.put(num, map.getOrDefault(num, 0) + 1);//統計元素出現頻次
 for (Integer num : nums2) {//周遊另一個數組
 if (map.containsKey(num)) {
 int tmp = map.get(num)-1;//頻次減一
 if (tmp == 0) map.remove(num);//頻次為 0 時,移出 HashMap
 else map.put(num, tmp);//否則更新頻次
 list.add(num);//加入動态數組
 }
 }
 //轉為數組并傳回
 int size=list.size();
 int[] res = new int[size];
 for (int i = 0; i < size; i++) res[i] = list.get(i);
 return res;
 }}
           

Python:

class Solution:
 def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
 count = dict(collections.Counter(nums1))# 自帶庫統計元素出現頻次,并轉為 Dict 類型
 res = []
 for num in nums2:# 周遊另一個數組
 if num in count:
 count[num] -= 1# 詞頻減一
 res.append(num)
 if count[num] <= 0:# 詞頻為 0 時,移出字典
 count.pop(num)
 return res
           

雙指針解題:

class Solution {
 public int[] intersect(int[] nums1, int[] nums2) {
 List<Integer> list = new ArrayList<>();
 Arrays.sort(nums1);//排序數組
 Arrays.sort(nums2);
 int i = 0, j = 0;//定義指針
 while (i < nums1.length && j < nums2.length) {
 if (nums1[i] < nums2[j]) i++;//移動較小數的指針
 else if (nums1[i] > nums2[j]) j++;//移動較小數的指針
 else {
 //兩數相等則為交集,存入動态數組,移動雙指針
 list.add(nums1[i]);
 i++;
 j++;
 }
 }
 //轉為數組并傳回
 int[] res = new int[list.size()];
 for (int k = 0; k < list.size(); k++) res[k] = list.get(k);
 return res;
 }}
           

class Solution:

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:

i, j, nums1_size, nums2_size = 0, 0, len(nums1), len(nums2)# 定義指針,計算數組長度

nums1, nums2, res = sorted(nums1), sorted(nums2), []# 排序數組,初始化傳回數組 res

while i < nums1_size and j < nums2_size:# 循環條件為指針不溢出

if nums1[i] < nums2[j]:# 移動數值較小的指針

i += 1

elif nums1[i] > nums2[j]:# 移動數值較小的指針

j += 1

else:

res.append(nums1[i])# 數值相等,則為交集,移動雙指針

return res