12 ms binary search solution by only sorting one array, C++


  • 0
    X
    // Intersection of two arrays, binary search solution
    class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            if (nums1.size() == 0 || nums2.size() == 0) {
                vector<int> nullVector; return nullVector;
            }
            set<int> des;
            sort(nums2.begin(), nums2.end());
            for (auto n: nums1) {
                if ( binarySearch(nums2, n) != -1 ) {
                    des.insert(n);
                }
            }
            vector<int> res;
            for (auto d: des) res.push_back(d);
            return res;
        }
        
        int binarySearch(vector<int>& nums, int val) {
            int first = 0, last = nums.size() - 1;
            while (first <= last) {
                int middle = (first + last) / 2;
                if (nums[middle] == val) return middle;
                if (val < nums[middle])
                    last = middle - 1;
                else
                    first = middle + 1;
            }
            return -1;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.