这篇文章主要为大家展示了“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最小距离”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
原创文章，作者：745907710，如若转载，请注明出处：https://blog.ytso.com/224020.html