查找第K个最小对距离-分析

Question

问题：

这是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的讨论论坛上找到了它。但是我很难理解代码的关键部分。

下面的代码基本上是在做一个二分搜索法。< code >低是最小距离,< code >高是最大距离。像通常的二分搜索法一样计算一个< code>mid。然后，它< code>countPairs(a，mid)查找绝对差小于或等于< code>mid的对的数量。然后相应地调整< code >低和< code >高。

但是为什么二分搜索法结果一定是距离之一呢？起初，从数组中得到< code>low和< code>high，但是< code>mid是由它们计算的，它可能不是距离。最后，我们返回< code>low，其值在基于< code>mid 1的二分搜索法期间发生变化。为什么< code>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;
    }
}

Answer 1

出于兴趣，我们可以在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

我们需要有效地确定和排序所有不同的可实现的差异的计数。这类似于将系数为< code>[1，0，2]的多项式乘以系数为< code>[2，0，0]的多项式(我们不需要第二组中的零系数，因为它仅生成小于或等于< code>T的度数)，这可以通过快速傅立叶变换在< code>m log m时间内完成，其中< code>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的差异。也许有人会建议，有一种简便的方法来计算零超额计数。我花了一些时间，但还没有分辨出一个。

在任何情况下，使用不相交重复计数可以很容易地获得零差异的计数，这允许我们仍然返回O（n log n m m log m）总时间中的k个差值。

Answer 2

这种类型的二进制搜索将找到第一个值 x，其计数对（a，x）

因此，当函数以最终值低终止时，我们知道当距离从low-1变为低时，对数会发生变化，因此必须存在一对距离较低的对。

例如，假设我们的目标是100，并且知道:

countPairs(a,9) = 99
countPairs(a,10) = 100

必须有一对距离正好为10的数字，因为如果没有这样的数字对，那么距离小于或等于10的数字对的数量将与距离小于或大于9的数字对数量相同。

请注意，这只适用于循环运行，直到测试间隔完全耗尽。如果代码使用了提前终止条件，如果找到准确的目标值，则会退出循环，那么它可能会返回错误的答案。