leetcode如何找出第k最小距離

發(fā)布時間：2021-12-16 09:30:00 來源：億速云閱讀：151 作者：小新欄目：大數(shù)據(jù)

這篇文章主要為大家展示了“l(fā)eetcode如何找出第k最小距離”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學習一下“l(fā)eetcode如何找出第k最小距離”這篇文章吧。

給定一個整數(shù)數(shù)組，返回所有數(shù)對之間的第 k 個最小距離。一對 (A, B) 的距離被定義為 A 和 B 之間的絕對差值。

示例 1:

輸入：
nums = [1,3,1]
k = 1
輸出：0 
解釋：
所有數(shù)對如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 個最小距離的數(shù)對是 (1,1)，它們之間的距離為 0。

提示:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

對于第k?。ù螅┑膯栴}首先想到的是堆，對于第k小用大根堆。

1,二叉堆是一根完全二叉樹，可以用數(shù)組實現(xiàn)，如果i％2=＝0 則父節(jié)點為i/2－1，否則為i/2

2,堆每次插入元素都是放到數(shù)組末尾，然后與父節(jié)點比較，如果比父節(jié)點大，則交換，一直到根節(jié)點。

3，刪除元素，每次都是取出堆頂元素，然后將數(shù)組末尾元素放到堆頂，如果堆頂新元素小于任何一個孩子，則與孩子中交大者交換，直到葉子節(jié)點

4，對于本題，可以設(shè)置大小為k的大頂堆，當堆未滿進行2，3步，如果堆滿，比較插入元素和堆頂，如果比堆頂大不考慮，否則刪除堆頂，然后插入堆尾。

func smallestDistancePair(nums []int, k int) int {  if len(nums) < 0 {    return 0  }    var h heap    h.length=k  for 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 []int    length 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) - 1  p := getP(i)  for i > 0  && h.data[p] < h.data[i]{    h.data[p], h.data[i] = h.data[i], h.data[p]    i = p    p = 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 := 0  for 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，這是一個內(nèi)存和效率折衷的方案，本題要求效率，所以可以采用hash計數(shù)

func smallestDistancePair(nums []int, k int) int {  if len(nums) < 0 {    return 0  }    var a [1000000]int  for 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:=0    for ;i<1000000;i++{        if a[i]>=k{            return i        }        k-=a[i]    }    return -1}

以上是“l(fā)eetcode如何找出第k最小距離”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！

向AI問一下細節(jié)

leetcode如何找出第k最小距離

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標簽