找到Kth最小的对距离 - 分析

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论坛上找到的代码.但我无法理解代码的关键部分.

下面的代码基本上是进行二进制搜索.这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

这种类型的二分查找将找到countPairs(a,x) >= k 的第一个值 x。（topcoder 教程很好地解释了这一点。）

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

例如，假设我们的目标为 100 并且知道：

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

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

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