# Kth-Pair-Distance

## 题目地址（822. Kth-Pair-Distance）

https://binarysearch.com/problems/Kth-Pair-Distance

## 题目描述

``````Given a list of integers nums and an integer k, return the k-th (0-indexed) smallest abs(x - y) for every pair of elements (x, y) in nums. Note that (x, y) and (y, x) are considered the same pair.

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 5, 3, 2]
k = 3
Output
2
Explanation
Here are all the pair distances:

abs(1 - 5) = 4
abs(1 - 3) = 2
abs(1 - 2) = 1
abs(5 - 3) = 2
abs(5 - 2) = 3
abs(3 - 2) = 1
Sorted in ascending order we have [1, 1, 2, 2, 3, 4].``````

• 排序

• 二分法

## 堆（超时）

### 代码

Python3 Code:

``````class Solution:
def solve(self, A, k):
A.sort()
h = [(A[i] - A[i-1], i-1,i) for i in range(1, len(A))]
heapq.heapify(h)

while True:
top, i, j = heapq.heappop(h)
k -= 1
if j + 1 < len(A): heapq.heappush(h, (A[j+1] - A[i], i, j + 1))``````

## 二分法

### 思路

1. p 小于 k，那么可舍弃一半解空间

2. p 大于 k，同样可舍弃一半解空间

• 确定解空间上下界

• 如果计算小于等于 diff 的有即可

### 代码

Python3 Code:

``````class Solution:
def solve(self, A, k):
A.sort()
def count_not_greater(diff):
i = ans = 0
for j in range(1, len(A)):
while A[j] - A[i] > diff:
i += 1
ans += j - i
return ans
l, r = 0, A[-1] - A[0]

while l <= r:
mid = (l + r) // 2
if count_not_greater(mid) > k:
r = mid - 1
else:
l = mid + 1
return l``````

• 时间复杂度：由于进行了排序， 因此时间复杂度大约是 \$O(nlogn)\$

• 空间复杂度：取决于排序的空间消耗