Kth-Pair-Distance

# 题目描述

1
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.
2
3
Constraints
4
5
n ≤ 100,000 where n is the length of nums
6
Example 1
7
Input
8
nums = [1, 5, 3, 2]
9
k = 3
10
Output
11
2
12
Explanation
13
Here are all the pair distances:
14
15
abs(1 - 5) = 4
16
abs(1 - 3) = 2
17
abs(1 - 2) = 1
18
abs(5 - 3) = 2
19
abs(5 - 2) = 3
20
abs(3 - 2) = 1
21
Sorted in ascending order we have [1, 1, 2, 2, 3, 4].
Copied!

• 排序
• 二分法

# 堆（超时）

## 代码

Python3 Code:
1
class Solution:
2
def solve(self, A, k):
3
A.sort()
4
h = [(A[i] - A[i-1], i-1,i) for i in range(1, len(A))]
5
heapq.heapify(h)
6
7
while True:
8
top, i, j = heapq.heappop(h)
9
10
k -= 1
11
if j + 1 < len(A): heapq.heappush(h, (A[j+1] - A[i], i, j + 1))
Copied!

# 二分法

## 思路

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

• 确定解空间上下界
• 如果计算小于等于 diff 的有即可

## 代码

Python3 Code:
1
class Solution:
2
def solve(self, A, k):
3
A.sort()
4
def count_not_greater(diff):
5
i = ans = 0
6
for j in range(1, len(A)):
7
while A[j] - A[i] > diff:
8
i += 1
9
ans += j - i
10
return ans
11
l, r = 0, A[-1] - A
12
13
while l <= r:
14
mid = (l + r) // 2
15
if count_not_greater(mid) > k:
16
r = mid - 1
17
else:
18
l = mid + 1
19
return l
Copied!

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