Leetcode 719. Find K-th Smallest Pair Distance

[Woodyiiiiiii]

Leetcode 719. Find K-th Smallest Pair Distance

719. Find K-th Smallest Pair Distance

Institution

这道题我一开始想用堆来做，但发现绕不开pair，因为要遍历所有的pair，这样肯定不行的。

那么就要换另一种做法了。我要向另一种方法巧妙地绕过pair的限制，不需要遍历所有的pair，也就是说，只有一次遍历。(Sliding Window?

根据我们已有的条件，我们有数组，有最大距离，最小距离，有k值，所以也就想到二分法结合滑动窗口去逼近k。

Complexity

Time: O(nlogn + mlogm)
Space: O(1)

Code

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int r = nums[n - 1] - nums[0] + 1;
        int l = r;
        for (int i = 1; i < n; i++) {
            l = Math.min(l, nums[i] - nums[i - 1]);
        }
        while (l < r) {
            int m = (l + r) >> 1;
            if (countWithin(nums, n, m) >= k) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    private int countWithin(final int[] nums, final int n, int m) {
        int ll = 0, rr = 1, cnt = 0;
        while (rr < n) {
            while (ll < rr && nums[rr] - nums[ll] > m) {
                ll++;
            }
            cnt += (rr - ll);
            rr++;
        }
        return cnt;
    }
}