🔗 🟢 350. Intersection of Two Arrays II

題意

給定兩個整數陣列 nums1nums1 和 nums2nums2，以陣列形式返回它們交集的陣列。

返回結果中的每個元素出現的次數，應與元素在兩個陣列中都出現的次數一樣多。可以按照任意順序返回結果。

約束條件

  • 1≤nums1.length,nums2.length≤10001 \leq nums1.length, nums2.length \leq 1000
  • 0≤nums1[i],nums2[i]≤10000 \leq nums1[i], nums2[i] \leq 1000

思路

方法一：基於值域或對索引取交集

由於每個數字出現的次數可能不只一次，我們需要記錄每個數字出現的次數。

注意到 nums1nums1 和 nums2nums2 中的數字範圍是 00 到 10001000，我們可以使用這個特性來解決這個問題。

令 cnt1cnt1 和 cnt2cnt2 分別是長度為 10011001 的計數陣列，用來記錄 nums1nums1 和 nums2nums2 中每個數字出現的次數。

則遍歷值域 00 到 10001000，對於每個數字 xx，其在交集陣列出現的次數為 min⁡(cnt1[x],cnt2[x])\min(cnt1[x], cnt2[x])。因此，我們只需要在答案陣列中添加 min⁡(cnt1[x],cnt2[x])\min(cnt1[x], cnt2[x]) 個 xx 即可。

這個思路也能使用雜湊表來實現，對在 cnt1cnt1 和 cnt2cnt2 中的索引取交集，然後將交集中的數字按照次數添加到答案陣列中即可。

複雜度分析

  • 時間複雜度：O(n+m+D)\mathcal{O}(n + m + D)，其中 nn 和 mm 分別是 nums1nums1 和 nums2nums2 的長度，DD 是值域大小，本題中為 10011001。
  • 空間複雜度：O(D)\mathcal{O}(D)，需要額外的空間來存儲兩個計數陣列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # return list((Counter(nums1) & Counter(nums2)).elements())
        cnt1 = [0] * 1001
        cnt2 = [0] * 1001
        for x in nums1:
            cnt1[x] += 1
        for x in nums2:
            cnt2[x] += 1
        
        ans = []
        for x in range(1001):
            ans += [x] * min(cnt1[x], cnt2[x])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> cnt1(1001), cnt2(1001);
        for (int x : nums1) cnt1[x]++;
        for (int x : nums2) cnt2[x]++;
        vector<int> ans;
        for (int x = 0; x <= 1000; x++) {
            for (int i = 0; i < min(cnt1[x], cnt2[x]); i++) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

方法二：雜湊表(Hash Table)

方法一中我們先遍歷兩個陣列，然後再遍歷值域或索引的交集，但若 x∈nums1∧x∉nums2∨x∉nums1∧x∈nums2x \isin nums1 \land x \notin nums2 \lor x \notin nums1 \land x \isin nums2 ，則不需要考慮 xx 。因此只需要遍歷兩個陣列各一次即可。

同樣先遍歷一次 nums1nums1 ，令 cnt1cnt1 為 nums1nums1 中每個數字出現的次數。在遍歷 nums2nums2 的時候，對於每個數字 xx ，若 cnt1[x]>0cnt1[x] > 0 ，則將 xx 加入答案陣列中，並將 cnt1[x]cnt1[x] 減一。

計數的方式可以用 雜湊表(Hash Table) 來實現，但由於值域是 00 到 10001000 ，也可以使用一個長度為 10011001 的陣列來實現。

複雜度分析

  • 時間複雜度：O(n+m)\mathcal{O}(n + m)，其中 nn 和 mm 分別是 nums1nums1 和 nums2nums2 的長度。
  • 空間複雜度：O(n)\mathcal{O}(n) 或 O(D)\mathcal{O}(D) 。
    • 若使用雜湊表，空間複雜度是 O(n)O(n) 。
    • 若使用計數陣列，空間複雜度是 O(D)O(D) 。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # cnt = defaultdict(int)
        cnt = [0] * 1001
        for x in nums1:
            cnt[x] += 1
        ans = []
        for x in nums2:
            if cnt[x] > 0:
                ans.append(x)
                cnt[x] -= 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        // unordered_map<int, int> cnt;
        vector<int> cnt(1001);
        for (int x : nums1) cnt[x]++;
        vector<int> ans;
        for (int x : nums2) {
            if (cnt[x] > 0) {
                ans.push_back(x);
                cnt[x]--;
            }
        }
        return ans;
    }
};

方法三：排序(Sorting) + 雙指針(Two Pointers)

若 nums1nums1 和 nums2nums2 都是有序的，則可以使用 雙指針(Two Pointers) 的方式來解決這個問題。

首先對 nums1nums1 和 nums2nums2 進行排序，然後使用兩個指針 ii 和 jj 分別指向 nums1nums1 和 nums2nums2 的開頭。

  • 若 nums1[i]<nums2[j]nums1[i] < nums2[j] ，則 ii 往右移動。
  • 若 nums1[i]>nums2[j]nums1[i] > nums2[j] ，則 jj 往右移動。
  • 若 nums1[i]=nums2[j]nums1[i] = nums2[j] ，則將 nums1[i]nums1[i] 加入答案陣列中，並將 ii 和 jj 同時往右移動。

複雜度分析

  • 時間複雜度：O(nlog⁡n+mlog⁡m)\mathcal{O}(n \log n + m \log m)，其中 nn 和 mm 分別是 nums1nums1 和 nums2nums2 的長度。
    • 若已經是有序的，則時間複雜度是 O(n+m)\mathcal{O}(n + m)。
  • 空間複雜度：O(1)\mathcal{O}(1)，忽略排序的空間複雜度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
    
        m, n = len(nums1), len(nums2)
        i, j = 0, 0
        ans = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                ans.append(nums1[i])
                i += 1
                j += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        int m = nums1.size(), n = nums2.size();
        int i = 0, j = 0;
        vector<int> ans;
        while (i < m && j < n) {
            if (nums1[i] == nums2[j]) {
                ans.push_back(nums1[i]);
                i++, j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
};

寫在最後

Cover photo is remixed from @吃肥皂泡泡, thanks for their work!