349.两个数组的交集

🉐二分查找 and 哈希表

  一个哈希表的set来得到一个数组的唯一值，再通过二分查找来比较，得到一样的值，放入结果的vector中。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> st;
        if(!nums1.size() || !nums2.size()) 
            return vector<int>();
        vector<int> res;
        int lo, ho, mid;
        sort(nums2.begin(), nums2.end());
        for(auto x: nums1) 
            st.insert(x);
        for(auto x: st) {
            lo = 0;
            ho = nums2.size() - 1;
            while(lo < ho) {
                mid = lo + (ho - lo) / 2;
                if(nums2[mid] < x) {
                    lo = mid + 1;
                } else {
                    ho = mid;
                }
            }
            if(nums2[lo] == x) {
                res.push_back(x);
            }
        }
        return res;
    }
};