1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
func smallestDistancePair(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
// 统计差值 <= mid 的数对数量
countPairs := func(mid int) int {
count := 0
left := 0
for right := 0; right < n; right++ {
for nums[right]-nums[left] > mid {
left++
}
count += right - left
}
return count
}
// 二分查找答案
low, high := 0, nums[n-1]-nums[0]
for low < high {
mid := (low + high) / 2
if countPairs(mid) < k {
low = mid + 1
} else {
high = mid
}
}
return low
}
|