题：
这是LeetCode的一个问题：
给定整数数组，返回所有对中的第k个最小距离。一对（A，B）的距离定义为A和B之间的绝对差。
例：
Input:
nums = [1,3,1]
k = 1
Output: 0
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.
我的问题
我用天真的方法解决了它O（n ^ 2）基本上我找到了所有的距离然后对它进行排序然后找到最小的第k个。现在这是一个更好的解决方案。这不是我在leetcode论坛上找到的代码。但我无法理解代码的关键部分。
下面的代码基本上是进行二进制搜索。 low是最小距离，high是最大距离。像通常的二分搜索一样计算mid。然后它确实countPairs(a, mid)找到绝对差值小于或等于mid的对的数量。然后相应地调整low和high。
但为什么二进制搜索结果必须是距离之一？起初，low和high来自阵列，但mid，由他们计算，它可能不是距离。最后，我们返回low，其值在mid + 1的二进制搜索基础上发生变化。为什么mid + 1保证是距离之一？
class Solution {
// Returns index of first index of element which is greater than key
private int upperBound(int[] a, int low, int high, int key) {
if (a[high] <= key) return high + 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (key >= a[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Returns number of pairs with absolute difference less than or equal to mid.
private int countPairs(int[] a, int mid) {
int n = a.length, res = 0;
for (int i = 0; i < n; i++) {
res += upperBound(a, i, n - 1, a[i] + mid) - i - 1;
}
return res;
}
public int smallestDistancePair(int a[], int k) {
int n = a.length;
Arrays.sort(a);
// Minimum absolute difference
int low = a[1] - a[0];
for (int i = 1; i < n - 1; i++)
low = Math.min(low, a[i + 1] - a[i]);
// Maximum absolute difference
int high = a[n - 1] - a[0];
// Do binary search for k-th absolute difference
while (low < high) {
countPairs(a, mid)
if (countPairs(a, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
}
这种类型的二进制搜索将找到countPairs（a，x）> = k的第一个值x。 （topcoder tutorial很好地解释了这一点。）
因此，当函数终止于最终值为低时，我们知道当距离从低-1变为低时，对的数量会发生变化，因此必须有一对距离较低的对。
例如，假设我们的目标为100并且知道：
countPairs(a,9) = 99
countPairs(a,10) = 100
必须有一对距离恰好为10的数字，因为如果没有这样的对，那么距离小于或等于10的对的数量将与距离小于或等于9的对的数量相同。
请注意，这仅适用于循环运行，直到测试间隔完全耗尽。如果代码使用了提前终止条件，如果找到了确切的目标值则退出循环，那么它可能会返回错误的答案。
出于兴趣，我们可以使用快速傅里叶变换在O(n log n + m log m)时间解决这个问题，其中m是范围。
首先对输入进行排序。现在考虑通过从另一个中减去一个差异前缀和，可以实现数字之间可达到的每个距离。例如：
input: 1 3 7
diff-prefix-sums: 2 6
difference between 7 and 3 is 6 - 2
现在让我们将等式（最右边的前缀和）添加到等式的每一边：
ps[r] - ps[l] = D
ps[r] + (T - ps[l]) = D + T
我们列出差异：
1 1 3
0 2
和前缀总和：
p => 0 0 2
T - p => 2 2 0 // 2-0, 2-0, 2-2
我们需要有效地确定和排序所有不同可实现差异的计数。这类似于将多项式与系数[1, 0, 2]乘以多项式与系数[2, 0, 0]（我们不需要第二组中的零系数，因为它只生成小于或等于T的度数），我们可以在m log m时间完成，其中m是度，具有快速傅里叶变换。
结果系数为：
1 0 2
*
2 0 0
=>
x^2 + 2
*
2x^2
= 2x^4 + 4x^2
=> 2 0 4 0 0
我们丢弃低于T的度数，并显示我们的有序结果：
2 * 4 = 2 * (T + 2) => 2 diffs of 2
4 * 2 = 4 * (T + 0) => 4 diffs of 0
我们超过了0的差异。也许有一种方便的方法来计算某人可能建议的零过量。我花了一些时间，但尚未区分一个。
在任何情况下，使用不相交的重复计数可以容易地获得零差异的计数，这允许我们仍然返回k总时间中的O(n log n + m log m)th差异。