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
}