Code & Func

第82天。

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

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

Note: Each element in the result must be unique. The result can be in any order.

可以用排序做，也可以用hash做：

排序的做法：

1
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
2
    sort(nums1.begin(),nums1.end());
3
    sort(nums2.begin(),nums2.end());
4
    auto beg1 = nums1.begin();
5
    auto beg2 = nums2.begin();
6
    vector<int> ret;
7
    while(beg1 < nums1.end() && beg2 < nums2.end()) {
8
        if (*beg1 == *beg2) {
9
            int t  = *beg1;
10
            ret.push_back(t);
11
            while(beg1 < nums1.end() && *beg1 == t) beg1++;
12
            while(beg2 < nums2.end() && *beg2 == t) beg2++;
13
        } else if (*beg1 < *beg2) beg1++;
14
        else beg2++;
15
    }
2 collapsed lines
16
    return ret;
17
}

hash的做法：

1
vector<int> intersection1(vector<int>& nums1, vector<int>& nums2) {
2
    unordered_map<int,int> m;
3
    vector<int> ret;
4
    for(auto i:nums1) m[i]++;
5
    for(auto i:nums2)
6
        if (m.find(i) != m.end() && m[i]) {
7
            m[i] = 0;
8
            ret.push_back(i);
9
        }
10
    return ret;
11
}

dicuss还有用set做的:

1
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
2
    set<int> s(nums1.begin(), nums1.end());
3
    vector<int> out;
4
    for (int x : nums2)
5
        if (s.erase(x))
6
            out.push_back(x);
7
    return out;
8
}