L349 两个数组的交集

未分类

给定两个数组，编写一个函数来计算它们的交集。

解：数组n1,n2,给n1排序，遍历n2在n1中查找

• 若输出不重复，则用set特性，用完再转回为vector,
  vector(set.begin(),set.end());

• 若输出是重复的，则每找过一个就在n2中删除一个。

• set.insert()插入不重复的数字

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> res;
        // special case
        //if(nums1.empty()) return vector<int>(res.begin(),res.end());
        //if(nums2.empty()) return vector<int>(res.begin(),res.end()); 
        // sort one array2, find nums1 in nums2.
        sort(nums2.begin(),nums2.end());
        for(int i=0;i<nums1.size();i++){
            if (binarySearch(nums2,nums1[i])){
                    res.insert(nums1[i]);
            }
        }
        return vector<int>(res.begin(),res.end());
    }
    bool binarySearch(vector<int>& nums2, int target){
        int left=0,right=nums2.size()-1,mid;
        while(left <=right){
            mid = left + (right-left)/2;
            if(nums2[mid]==target){ return true;}
            if(nums2[mid] > target) right = mid-1;
            else left = mid+1;
        }
        return false;
    }
};