LeetCode 350. Intersection of Two Array

350. Intersection of Two Array
一、問題の説明
Given two arrays, write a function to compute their intersection.
Note:

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

The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

What if nums1’s size is small compared to nums2’s size? Which algorithm is better?

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?

二、入出力
Example: Given nums1 = [1, 2, 2, 1] , nums2 = [2, 2] , return [2, 2] .
三、問題を解く構想

以前に交差を探していた問題とは異なり、ここでは具体的に何度も現れても出力する必要がある.個人的な考えはまっすぐで,2つの配列をそれぞれ1つのmapに格納し,各要素の出現回数を記録する.合計n要素があると仮定すると,時間複雑度はo(n) mapの実装は赤黒樹であり,挿入複雑度はo(logn)である.その後、この2つのmapを巡って同じ要素を見つけ、出現した個数の小さいものを最終結果としてvectorに格納して返します.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> dict1, dict2;
        int n1 = nums1.size(), n2 = nums2.size();
        for (int i = 0; i < n1; ++i) {
            if(dict1.find(nums1[i]) == dict1.end()) dict1.insert(make_pair(nums1[i], 1));
            else dict1[nums1[i]]++;
        }
        for (int j = 0; j < n2; ++j) {
            if(dict2.find(nums2[j]) == dict2.end()) dict2.insert(make_pair(nums2[j], 1));
            else dict2[nums2[j]]++;
        }
        vector<int> ret;
        for (auto ite : dict1){
            int key = ite.first;
            int cnt = 0;
            map<int, int>::iterator ite2;
            if((ite2 = dict2.find(key)) != dict2.end()){
                cnt = min(ite.second, ite2->second);
            }
            for (int i = 0; i < cnt; ++i) {
                ret.push_back(key);
            }
        }
        return ret;
    }
};