文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 hash
    • 2.2 數組已排序

1. 題目

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

示例 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 的元素存儲在磁盤上，磁盤內存是有限的，并且你不能一次加載所有的元素到內存中，你該怎么辦？

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 hash

• 對數組1建立hash鍵值對，記錄元素出現次數
• 數組2在上面hash表中查找，找到了，push該數進入answer，并將hash表的值減1，當表的值為0時，不能再取該數
• 時間復雜度$O(n1+n2)$, 空間復雜度$O(n1)$

class Solution { public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> m1;int i;vector<int> ans;for(i = 0; i < nums1.size(); ++i){if(m1.find(nums1[i]) == m1.end())m1[nums1[i]] = 1;elsem1[nums1[i]]++;}for(i = 0; i < nums2.size(); ++i){if(m1.find(nums2[i]) != m1.end() && m1[nums2[i]] > 0){ans.push_back(nums2[i]);m1[nums2[i]]--;}}return ans;} };

2.2 數組已排序

• 如果數組已排序，雙指針，分別定位在數組首位
• $如果nums[i]>nums2[j],j++$
• $如果nums[i]<nums2[j],i++$
• $如果nums[i]=nums2[j],i++,j++$

如果nums1數組小，第二種方法更好，最壞時間復雜度$O(max(n1,n2))$

如果nums2數組很大，不能一次加載到內存，可以等分成x份，分別與nums1數組進行求交集

class Solution { public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());int i, j;vector<int> ans;for(i = 0, j = 0; i < nums1.size() && j < nums2.size(); ){if(nums1[i] < nums2[j])++i;else if(nums1[i] > nums2[j])++j;else// nums1[i] == nums2[j]{ans.push_back(nums1[i]);++i,++j;}}return ans;} };

總結

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

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