C++ twice binary search


  • 0
    B
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        int mid=0,head=0,tail=1000000;
        while(head<=tail)
        {
            mid=head+(tail-head)/2;
            int count=0;
            for(int i=0;i<nums.size();i++)
            {
                auto upper = upper_bound(nums.begin(), nums.end(), nums[i]+mid);
                count+=(upper-nums.begin())-i-1;
            }
            if(count<k)head=mid+1;
            else tail=mid-1;
        }
        return head;
    }

Log in to reply
 

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