溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了“leetcode如何找出第k最小距離”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“leetcode如何找出第k最小距離”這篇文章吧。
給定一個整數數組，返回所有數對之間的第 k 個最小距離。一對 (A, B) 的距離被定義為 A 和 B 之間的絕對差值。
示例 1:
輸入：
nums = [1,3,1]
k = 1
輸出：0
解釋：
所有數對如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 個最小距離的數對是 (1,1)，它們之間的距離為 0。
提示:
2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.
對于第k小（大）的問題首先想到的是堆，對于第k小用大根堆。
1,二叉堆是一根完全二叉樹，可以用數組實現，如果i％2=＝0 則父節點為i/2－1，否則為i/2
2,堆每次插入元素都是放到數組末尾，然后與父節點比較，如果比父節點大，則交換，一直到根節點。
3，刪除元素，每次都是取出堆頂元素，然后將數組末尾元素放到堆頂，如果堆頂新元素小于任何一個孩子，則與孩子中交大者交換，直到葉子節點
4，對于本題，可以設置大小為k的大頂堆，當堆未滿進行2，3步，如果堆滿，比較插入元素和堆頂，如果比堆頂大不考慮，否則刪除堆頂，然后插入堆尾。
func smallestDistancePair(nums []int, k int) int {if len(nums) < 0 {return 0}var h heaph.length=kfor i := 0; i < len(nums); i++ {for j := i + 1; j < len(nums); j++ {if nums[i] > nums[j] {h.handle(nums[i] - nums[j])} else {h.handle(nums[j] - nums[i])}}}return h.data[0]}type heap struct {data []intlength int}func (h *heap)handle(val int){if len(h.data)<h.length{h.insert(val)}else{if val<h.data[0]{h.pop()h.insert(val)}}}func (h *heap) insert(val int) {h.data = append(h.data, val)i := len(h.data) - 1p := getP(i)for i > 0 && h.data[p] < h.data[i]{h.data[p], h.data[i] = h.data[i], h.data[p]i = pp = getP(i)}}func getP(i int) int {if i%2 == 0 {return i/2 - 1}return i / 2}func (h *heap) pop() int {if len(h.data) < 1 {return 0}top := h.data[0]h.data[0] = h.data[len(h.data)-1]h.data = h.data[0 : len(h.data)-1]i := 0for 2*i+1 < len(h.data) {if 2*i+2 < len(h.data) {if h.data[2*i+1] > h.data[2*i+2] {h.data[i], h.data[2*i+1] = h.data[2*i+1], h.data[i]i = 2*i + 1} else {h.data[i], h.data[2*i+2] = h.data[2*i+2], h.data[i]i = 2*i + 2}} else {h.data[i], h.data[2*i+1] = h.data[2*i+1], h.data[i]i = 2*i + 1}}return top}
5，這是一個內存和效率折衷的方案，本題要求效率，所以可以采用hash計數
func smallestDistancePair(nums []int, k int) int {if len(nums) < 0 {return 0}var a [1000000]intfor i := 0; i < len(nums); i++ {for j := i + 1; j < len(nums); j++ {if nums[i] > nums[j] {a[nums[i] - nums[j]]++} else {a[nums[j] - nums[i]]++}}}i:=0for ;i<1000000;i++{if a[i]>=k{return i}k-=a[i]}return -1}
以上是“leetcode如何找出第k最小距離”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
