719. Find K-th Smallest Pair Distance
有一个矩阵nums和一个整数k
将nums中任意两个元素nums[i]、nums[j]的差值(绝对值)
进行排序，请回传第k小的差值
思路:
跟8/4号的每日1508. Range Sum of Sorted Subarray Sums基本一样
就透过二分搜寻去找出第k小的差值
先对nums进行排序
最小的差值一定不会比0小
最大的差值就是nums[n-1]-nums[0]
所以设L=0、R=nums[n-1]-nums[0]、M=L+(R-L)/2
就用two pointer去算差值小于M的有几个
如果比k少那L=M+1
不然就R=M
这样就可以找到答案了
GOLANG CODE :
func smallestDistancePair(nums []int, k int) int {
n := len(nums)
slices.Sort(nums)
l, r := 0, nums[n-1]-nums[0]
for r > l {
m := l + (r-l)/2
cnt := 0
i, j := 0, 1
for i < n {
for j < n && nums[j]-nums[i] <= m {
j++
}
cnt += j - i - 1
i++
}
if cnt < k {
l = m + 1
} else {
r = m
}
}
return l
}