# 「力扣」第 719 题：找出第 k 小的距离对（困难）
# 同时使用了「二分查找」与「滑动窗口」的一道问题
在准备滑动窗口的过程中，做到了一道不错的问题，在这里和大家分享一下。这道题是：「力扣」第 719 题：找出第 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：
输入：nums = [1,1,1], k = 2
输出：0
示例 3：
输入：nums = [1,6,1], k = 3
输出：5
提示:
2 <= len(nums) <= 10000.0 <= nums[i] < 1000000.1 <= k <= len(nums) * (len(nums) - 1) / 2.
# 1. 解释题意
- 注意题目中的关键字：整数数组；
- 数对的距离定义为：两个数的差的绝对值。由于输入数组是整数数组，因此数对的距离一定为非负整数；
- 根据「示例 2」，数组中所有的数都是
，距离只能为 ，但题目偏偏要问 ，说明：「第 小的距离对」不是「第 小的不同距离对」。类似问题的问法还有「力扣」第 378 题：有序矩阵中第 小的元素。注意到这一点很重要。因此题目最后给出的数据范围是 1 <= k <= len(nums) * (len(nums) - 1) / 2。
# 2. 暴力解法
计算所有的数对的距离（时间复杂度
# 3. 思路分析
为什么想到「二分查找」？ 题目要求返回一个整数（注意输入数组是 整数数组），并且这个整数是 有范围 的，因此可以考虑使用「二分查找」找到这个有范围的整数。
「二分查找」的思路是这样的：先猜答案是某个整数 a，然后遍历输入数组：
- 如果距离 小于等于
a的数对的个数< k，a肯定是不是第k小的距离，此时说明猜的数a太小了； - 如果距离 小于等于
a的数对的个数= k，此时说明 猜的数a有可能是第k小的距离，不过也有可能猜的数a不是第k小的距离，但是答案最多是a。这里大家可以自己先思考一下，具体细节我们会在题解最后会给出解释； - 如果距离 小于等于
a的数对的个数> k，此时说明猜的数a太大了。
友情提示：二分查找向左走、还是向右走、猜的数有没有可能是答案，这些问题需要我们仔细分析。
# 4. 为什么想到「滑动窗口」？
题目要我们找到 所有 数对的最小距离。注意到这样的事实：如果 一个整数区间 里，「最小数」和「最大数」的差值为
例如：整数区间
因此我们 需要先对输入整数数组排序，以便快速计算「差值小于等于某个整数的数对的个数」，然后使用「滑动窗口」计算有序数组里，所有差值小于等于某个数的数对的个数。
# 5. 如何使用「滑动窗口」找到「距离」小于等于某个值的所有数对的个数
前提：输入数组升序排序。由于输入升序排序，距离 小于等于某个值的区间在整个输入数组上是连续的。因此可以通过「滑动窗口」一次遍历，找到这些连续的区间。
计算连续区间构成的数对的个数，可以在窗口滑动的时候使用加法，需要注意的一点是 保证计数不重不漏。
我们看一个例子，在有序数组
计数方法是这样的：枚举右端点。新扩展的右端点 和 原先滑动窗口里的每一个数组成数对，因此 只有当右边界向右移动的时候，才计算符合条件的数对的个数。
每一次找到数对的个数恰好是滑动窗口 [left..right] 表示的区间的长度（right - left + 1）再减 right 所在的位置），即 right - left 的值。
参考代码：
import java.util.Arrays;
public class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int len = nums.length;
int left = 0;
int right = nums[len - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
int count = countLessEquals(nums, mid);
if (count < k) {
// 如果小于等于 mid 的个数严格小于 k 个，说明 mid 太小了
// 下一轮搜索区间为 [mid + 1..right]
left = mid + 1;
} else {
// 下一轮搜索区间为 [left..mid]
right = mid;
}
}
return left;
}
/**
* 统计距离（数值之差）小于等于 target 的个数
*
* @param nums
* @param target
* @return
*/
private int countLessEquals(int[] nums, int target) {
int count = 0;
int len = nums.length;
for (int left = 0, right = 0; right < len; right++) {
while (nums[right] - nums[left] > target) {
left++;
}
// 此时满足 nums[right] - nums[left] <= target
// right 与 [left..right - 1] 里的每一个元素的「距离」都小于等于 target
// [left..right - 1] 里元素的个数为 right - left
count += right - left;
}
return count;
}
}
时间复杂度：
使用 nums 的最小值和最大值的差值。
- 排序：
； - 二分查找：
，二分查找每一轮 countLessEquals()函数需要遍历整个输入数组，两个变量遍历。
因此总的时间复杂度为
不知道大家在使用二分查找的过程中是否有以下疑问。
# 为什么「二分查找」一定保证了找到的值在距离数组中？
这里距离数组的意思是对输入数组排序以后，相邻元素的差组成的数组。例如输入数组 [3,6,7,10,13,19,24] （已经有序）的距离数组为 [3,1,3,3,6,5]。
也就是下面这段代码：
if (count < k) {
// 如果小于等于 mid 的个数严格小于 k 个，说明 mid 太小了
// 下一轮搜索区间为 [mid + 1..right]
left = mid + 1;
} else {
// 下一轮搜索区间为 [left..mid]
right = mid;
}
为什么可以保证区间 [left..right] 逐渐缩小到 left 与 right 重合的时候，left 一定在距离数组当中。
我们具体解释一下这段代码：
情况 1：
如果小于等于 mid 的距离对的个数 严格小于 k，此时 mid 肯定不是第 k 小的距离，第 k 小的距离肯定比 mid 大，因此下一轮搜索的区间是 [mid + 1..right]，此时设置 left = mid + 1。
情况 2：
如果小于等于 mid 的距离对的个数恰好等于 k，此时 mid 有可能是第 k 小的距离。
我们还用具体的例子还讲解这件事情，输入数组 [3,6,7,10,13,19,24] （已经有序）的距离数组为 [3,1,3,3,6,5]。
- 距离数组中小于等于
4的元素的个数为4，此时4不在距离数组中； - 距离数组中小于等于
3的元素的个数也等于4，此时我们知道3在距离数组中。
因此，二分查找如果找到了一个值，距离小于等于它的个数恰好等于 k 的时候，不能停止搜索，应该继续搜索下去。即：
如果小于等于 mid 的距离对的个数小于等于 k 时，mid 有可能是我们要找的目标值，也有可能不是。如果不是，目标元值只可能比 mid 小。因此下一轮搜索的区间为 [left..mid] ，此时设置 right = mid。
情况 3：
如果小于等于 mid 的距离对的个数严格大于 k，此时 mid 一定不是第 k 小的距离，第 k 小的距离一定比 mid 小，因此下一轮搜索的区间为 [left..mid - 1] ，此时设置 right = mid - 1。
二分查找的代码合并了「情况 2」和「情况 3」。
# 为什么二分查找分三种情况讨论的结果需要合并？
这里和大家提及一下为什么二分查找虽然可以分三种情况讨论，但是写代码的时候需要合并成两种情况。
结论是：如何不合并的话，在最后一轮搜索区间只有两个数的时候，如果不合并有可能会造成 left 和right 在退出以后不能重合。
这是因为，当搜索区间 [left..right] 里只有 2 个元素的时候：
- 如果划分区间的逻辑是
left = mid + 1;和right = mid;时，while(left < right)退出循环以后left == right成立，此时mid中间数正常下取整就好； - 如果划分区间的逻辑是
left = mid;和right = mid - 1;时，while(left < right)退出循环以后left == right成立，此时为了避免死循环，mid中间数需要改成上取整。
这一点是我今年在「力扣」第 34 题题解区和网友朋友们的讨论得到的。经常和网友讨论问题，会有不少收获。
# 相关问题
- 「力扣」第 713 题：乘积小于 K 的子数组（中等）
说明：这道问题需要弄清楚如何计数。
- 「力扣」第 992 题： K 个不同整数的子数组（困难）
说明：这道问题需要弄清楚如何计数。
- 「力扣」第 378 题：有序矩阵中第 K 小的元素（中等）
说明：这道问题很多朋友对为什么二分查找，找到的第 K 小的元素一定在矩阵中有疑惑。原因和本题的分析是一样的，用几个具体的例子分析就不难得出结论。
作者：liweiwei1419 链接：https://suanfa8.com/binary-search/solutions-2/0719-find-k-th-smallest-pair-distance 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。