# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/719-find-k-th-smallest-pair-distance.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.