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

Question

问题:

这是LeetCode的一道题:

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and 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;
    }
}

Answer 1

这种类型的二分搜索将找到 第一个 值 x，其中 countPairs(a,x) >= k。 (topcoder tutorial 解释得很好。)

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

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

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

必须有一对距离恰好为 10 的数字，因为如果没有这样一对，则距离小于或等于 10 的对数与距离小于或等于 10 的对数相同等于 9。

请注意，这仅适用，因为循环一直运行到被测时间间隔完全耗尽。如果代码改为使用提前终止条件，即在找到准确的目标值时退出循环，那么它可能会返回不正确的答案。