719.找出第 k 小的距离对

两天宇宙人

2020-02-21

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int left = 0,
            right = nums.back() - nums.front(), mi;
        while(left < right) {
            mi = left + (right - left) / 2;
            int count = 0;
            int start = 0; 
            for(int i = 0;i < nums.size(); ++i) {
                while(nums[i] - nums[start] > mi) {
                    ++start;
                }
                count += i - start;
            }
            if(count < k) { //如果小于K个
                left = mi + 1;
            } else {
                right = mi;
            }
        }
        return left;
    }
};