Fast Concise C++ double binary search


  • 0
    Q
    class Solution {
        int nLessThanEqual(vector<int>& nums, int mid)
        {
            int n=0;
            for(int i=0; i<nums.size(); ++i)
                n+=upper_bound(nums.begin()+i, nums.end(), nums[i]+mid)-nums.begin()-i-1;
            return n;
        }
    public:
        int smallestDistancePair(vector<int>& nums, int k) {
            
            sort(nums.begin(), nums.end());
            
            int b=0, e=nums.back()-nums.front();
            
            while(b<e)
            {
                int mid=b+(e-b)/2;
                
                if( nLessThanEqual(nums, mid) < k )
                    b=mid+1;
                else 
                    e=mid;
            }
            
            return b;
        }
    };
    

Log in to reply
 

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