2020-01-09 *找出第 k 小的距离对

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

示例 1:

输入：

nums = [1,3,1]
k = 1

输出：0
解释：
所有数对如下：

(1,3) -> 2
(1,1) -> 0
(3,1) -> 2

因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。
提示:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

C++1

二分法

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        // 转化为差
        int left = 0, right = nums[len - 1] - nums[0];

        while(left < right){
            int mid = left + (right - left) / 2;
            int count = getCount(nums, mid);
            if(count < k)   
                left = mid + 1;
            else            
                right = mid;
        }

        return left;
    }
    
    //计数方式
    int getCount(vector<int>& nums, int mid){
        int count = 0;
        int left = 0;
        for(int i = 1; i < nums.size();i++){
            while(nums[i] - nums[left] > mid)   
                left++;
            count += i - left;
        }

        return count;
    }
};