> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/719-find-k-th-smallest-pair-distance.md).

# 719     Find K-th Smallest Pair Distance

## 719. [Find K-th Smallest Pair Distance](https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/)

## 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](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/)一样，不同的是searchAndCount的逻辑不同，实在没想到。对于这种求第K小/大的题目中，如果其中包含某些带有顺序属性的性质，我们可以用二分法求出结果.

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

```java
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)

```java
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)