An O(NlogNlogN) time complexity algorithm(Using C++).


  • 1
    F
    class Solution {
    public:
        int bsa(int x){
            return x < 0 ? -x : x;
        }
        int countLessThan(vector<int>& nums, int x){
            int size = nums.size();
            int low, high, mid;
            int cnt = 0;
            for(int i = 0;i < size;++i){
                low = i, high = size;
                while(low < high - 1){
                    mid = (low + high) >> 1;
                    if(bsa(nums[i] - nums[mid]) <= x)low = mid;
                    else high = mid;
                }
                cnt += low - i;
            }
            return cnt;
        }
    
        int smallestDistancePair(vector<int>& nums, int k) {
            sort(nums.begin(), nums.end());
            int low = -2, high = 1 << 20, mid;
            while(low < high - 1){
                mid = (low + high) / 2;
                int cnt = countLessThan(nums, mid);
                if(cnt < k)low = mid;
                else high = mid;
            }
            return high;
        }
    };
    

Log in to reply
 

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