LeetCode 350. Intersection of Two Arrays II問題解(C++)

LeetCode 350. Intersection of Two Arrays II問題解(C++)
タイトルの説明

Given two arrays, write a function to compute their intersection.

例を挙げる

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

補足

Each element in the result should appear as many times as it shows in both arrays.

The result can be in any order.

構想

STLを使用した関連コンテナunordered_mapは、配列num 1を遍歴し、各要素が現れる回数をmapに記録する.

は配列num 2を遍歴し、その要素がmapテーブルで見つけられ、その要素がmapで対応する値が0より大きい場合、その要素は結果配列に入り、その要素がmapで対応する値を1から減算する.

コード#コード#

class Solution
{
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        unordered_map<int, int> hashMap;
        for (auto num : nums1)
        {
            hashMap[num]++;
        }
        vector<int> result;
        for (auto num : nums2)
        {
            if (hashMap.find(num) != hashMap.end() && hashMap[num] > 0)
            {
                result.push_back(num);
                hashMap[num]--;
            }
        }
        return result;
    }
};

Follow up

What if the given array is already sorted? How would you optimize your algorithm? 2つのポインタi,jが配列num 1,num 2をそれぞれ指すように昇順に並べられ、その後、2つのポインタが指す要素を比較し、num 1[i]=num 2[j]の場合、この数は交差し、pushは結果配列に入り、num 1[i]>num 2[j]の場合、jポインタは後方に移動し、num 1[i]

What if nums1’s size is small compared to nums2’s size? Which algorithm is better? 並べ替える場合は並べ替えるアルゴリズムを用い,並べ替えない場合はmapのアルゴリズムを用いる.

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once? 上のmapを使えば完成します.