Re: [閒聊] 每日leetcode
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.50.147 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723637198.A.80C.html
推
08/14 20:09,
1年前
, 1F
08/14 20:09, 1F
推
08/14 20:11,
1年前
, 2F
08/14 20:11, 2F
→
08/15 00:35,
1年前
, 3F
08/15 00:35, 3F
討論串 (同標題文章)
完整討論串 (本文為第 711 之 1548 篇)：