719 Find K-th Smallest Pair Distance

719. Find K-th Smallest Pair Distance

1. Question

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.

Example 1:

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.

Note:

1. 2 <= len(nums) <= 10000.

2. 0 <= nums[i] < 1000000.

3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

2. Implementation

(1) Binary Search

思路: 这题的居然思路和 Kth Smallest Element in a Sorted Matrix一样，不同的是searchAndCount的逻辑不同，实在没想到。对于这种求第K小/大的题目中，如果其中包含某些带有顺序属性的性质，我们可以用二分法求出结果.

二分的做法首先是找出输入数组中，最小的距离和最大的距离，最小距离显然是0， 最大距离则是最大数和最小数的差。在二分查找的过程中，我们先通过start和end取得一个中点mid，将mid作为一个target的距离，传入searchAndCount()中。searchAndCoutn()的作用是找出输入数组中，有多少对distance pair是小于或等于target. 如果searchAndCount()返回的数目小于k，说明mid小于第k个distance pair，更新start = mid + 1, 否则更新end = mid

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);

        int start = 0, end = nums[nums.length - 1] - nums[0], mid = 0;
        int count = 0;

        while (start < end) {
            mid = start + (end - start) / 2;

            count = searchAndCount(mid, nums);

            if (count < k) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return start;
    }

    public int searchAndCount(int target, int[] nums) {
        int count = 0;
        int start = 0;

        for (int end = 0; end < nums.length; end++) {
            while (nums[end] - nums[start] > target) {
                ++start;
            }
            count += end - start;
        }
        return count;
    }
}

(2) Heap (TLE)

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        PriorityQueue<PairDiff> minHeap = new PriorityQueue<>();

        for (int i = 1; i < nums.length; i++) {
            minHeap.add(new PairDiff(i - 1, i, Math.abs(nums[i - 1] - nums[i])));
        }

        int res = 0;

        for (int i = 0; i < k; i++) {
            PairDiff curDiff = minHeap.remove();

            int index1 = curDiff.index1;
            int index2 = curDiff.index2;
            res = curDiff.diff;

            if (index2 + 1 < nums.length) {
                minHeap.add(new PairDiff(index1, index2 + 1, Math.abs(nums[index1] - nums[index2 + 1])));
            }
        }
        return res;
    }

    class PairDiff implements Comparable<PairDiff> {
        int index1, index2, diff;

        public PairDiff(int index1, int index2, int diff) {
            this.index1 = index1;
            this.index2 = index2;
            this.diff = diff;
        }

        public int compareTo(PairDiff that) {
            return this.diff - that.diff;
        }
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度O(nlogn + (n^2) *logD), 其中D是数组中最大的diff的值，因为我们是在【0， maxDiff】这个space里进行二分搜索的

Heap: 时间复杂度O(nlogn + klogn), 空间复杂度O(n)