这篇文章主要为大家展示了“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 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，这是一个内存和效率折衷的方案，本题要求效率，所以可以采用hash计数
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}以上是“leetcode如何找出第k最小距离”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4586289/blog/4634828
