LeetCode_349. Intersection of Two Arrays

349. Intersection of Two Arrays Given two arrays, write a function to compute their intersection.
Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note: 1. Each element in the result must be unique. 2. The result can be in any order.
問題を解く構想:2つの構想を考えて、1つは先に重くして、それから1つずつ比較します;もう1つはmapで要素を統計することです.1つ目の実現の構想は簡単だが、効率的には2つ目に及ばないに違いない.まず1つ目を実現し、2つ目の具体的な実現はまだよく知られていない.
C++: version_1:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());//unique          ，       
        vector<int>::iterator iter1 = unique(nums1.begin(), nums1.end());
        nums1.erase(iter1, nums1.end());
        vector<int>::iterator iter2 = unique(nums2.begin(), nums2.end());
        nums2.erase(iter2, nums2.end());

        vector<int> sub;
        for (int i=0; ifor (int j=0; jif (nums1[i]==nums2[j])
                {
                    sub.push_back(nums1[i]);
                    break;
                }
            }
        }
        return sub;
    }
};

やはり効率は高くなく、46 msかかります.
version_2:map統計

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        vector<int> result;

        for (int i=0; imap[nums1[i]]++;
        }
        for (int i=0; iif (map[nums2[i]]>0)
            {
                result.push_back(nums2[i]);
                map[nums2[i]] = 0;  //          
            }
        }
        return result;
    }
};

Top Solution:所要時間8 ms!最初の方法より5、6倍速い!複数学習:
version_3:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> m(nums1.begin(), nums1.end());
        vector<int> res;
        for (auto a : nums2)
            if (m.count(a)) {
                res.push_back(a);
                m.erase(a);
            }
        return res;
    }
};

また、version_4:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    set<int> s(nums1.begin(), nums1.end());
    vector<int> out;
    for (int x : nums2)
        if (s.erase(x))
            out.push_back(x);
    return out;
}

この2つの方法はしばらく理解できないので、後でよく見てみましょう.