Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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
推 sustainer123: 大師
推 argorok: 大師
→ dont: 大師