LeetCode719. 找出第 k 小的距离对

☆☆☆☆☆（不是很理解....太绕了 T_T）

思路：二分 + 双指针。题目要求第K个最小距离，所以如果我们有一个有序数组记录着所有可能的最小距离，那么问题就可以变成一个最简单的二分法求解了

　　本题的难点在于二分查找的不是某个数，而是两个数的差值（即距离）。需要使用双指针来计算出所有小于等于mid的距离对数目。

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        /**
         *  思路：分两步求解，第一步 理清楚二分； 第二步 双指针计算出所有小于等于mid的距离对数目
         */
        Arrays.sort(nums);
        int len = nums.length;
        int low = 0, high = nums[len - 1] - nums[0];
        // 第 k 小的距离一定在最小距离 和 最大距离之间。
        while (low < high) {
            int mid = low + ((high - low) >> 1);
            int count = 0; // 记录所有<= mid 的距离对数目。
            int left = 0;
            for (int right = 0; right < len; right++) {
                while (nums[right] - nums[left] > mid) left ++;
                count += right - left;
            }
            if (count < k) {   //整个数列中比mid小的数列对的数量小于k个
                low = mid + 1; // 则第k个最小距离不会在[l,mid]之间，故修改l=mid+1；
            }else {
                high = mid;
            }
        }
        return low;
    }
}

参考：

动用「二分查找模板」来巧妙解决此题