Description

Submission

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> m1;
        map<int, int> m2;

        for(auto x: nums1) {
            ++m1[x];
        }

        for(auto x: nums2) {
            ++m2[x];
        }

        auto it1 = m1.begin();
        auto it2 = m2.begin();

        vector<int> rets;
        while(it1 != m1.end() && it2 != m2.end()) {
            if(it1->first < it2->first) {
                ++it1;
            } else if(it1->first > it2->first) {
                ++it2;
            } else {
                int t = min(it1->second, it2->second);

                for(int i = 0; i < t; ++i) {
                    rets.push_back(it1->first);
                }
                ++it1;
                ++it2;
            }
        }
        return rets;
    }
};