350. Intersection of Two Arrays II

這道題目要求我們找出兩個整數數列的交集，包括重複元素。具體來說:

1. 給定兩個整數數列 nums1 和 nums2。
2. 返回一個數列，包含兩個數列的交集元素。
3. 結果中每個元素出現的次數，應該與它在兩個數列中出現次數的最小值一致。
4. 結果可以按任意順序返回。

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

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

解決這個問題的一種常見方法是使用 HashMap 來記錄元素出現的次數。基本步驟如下:

1. 走訪 nums1，用 HahsMap 記錄每個元素出現的次數。
2. 走訪 nums2，檢查每個元素是否在 HashMap 中，如果在且次數大於 0，則加入結果數列,並將 HashMap 中該元素的計數減 1。

• Map

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        if (nums1.size() > nums2.size()) return intersect(nums2, nums1);

        unordered_map<int, int> m;

        for (int num : nums1) ++m[num];
        int k = 0;
        for (int num : nums2)
        {
            if (m.count(num) && m[num] >= 1)
            {
                --m[num];
                nums1[k++] = num;
            }
        }
        return vector<int>{nums1.begin(), nums1.begin() + k};
    }
};

• T: $O(n + m)$

• S: $O(min(n, m))$

• Sort

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        int i = 0, j = 0, k = 0;
        while (i < nums1.size() && j < nums2.size())
        {
            if (nums1[i] < nums2[j])
            {
                ++i;
            }
            else if (nums1[i] > nums2[j])
            {
                ++j;
            }
            else
            {
                nums1[k++] = nums1[i++];
                ++j;
            }

        }
        return vector<int>{nums1.begin(), nums1.begin() + k};
    }
};

• T: $O(n \log n + m \log m)$
• S: $O(\log n + \log m)$