719.找出第 k 小的距离对 (Hard)*

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int l = 0, r = nums[n - 1] - nums[0];
        while(l < r) {
            int mid = l + (r - l) / 2;
            int cnt = 0;
            int idx = n - 1;
            for(int i = n - 2; i >= 0; i--) {
                while(idx > i && nums[idx] - nums[i] > mid) {
                    idx--;
                }
                cnt += idx - i;
            }

            if(cnt < k) {
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        return l;
    }
};