千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

导航： 首页 > 互联网科技 >

leetcode如何找出第k最小距离

发表于：2026-11-01 作者：千家信息网编辑
千家信息网最后更新 2026年11月01日，这篇文章主要为大家展示了"leetcode如何找出第k最小距离"，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下"leetcode如何找出第k最小距离"这篇文章
千家信息网最后更新 2026年11月01日leetcode如何找出第k最小距离

这篇文章主要为大家展示了"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。

提示:

  1. 2 <= len(nums) <= 10000.

  2. 0 <= nums[i] < 1000000.

  3. 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.insert(val)    }else{        if val            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最小距离"这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！

很赞哦！
元素 最小 节点 数组 之间 内容 篇文章 孩子 效率 末尾 本题 j++ 学习 帮助 交大 内存 叶子 大小 差值 整数 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 互联网科技 互联网络科技 深圳九邦互联网科技有限公司 以房互联网科技 齐家互联网科技有限公司 开启互联网科技时代小说 恒银科技与互联网金融 深圳市优智互联网科技有限公司 内蒙古九一互联网科技 科技大学互联网 合肥互联网科技公司公章图片 2021互联网科技公司排名 互联网领先科技宣传片 中国新注册互联网科技 互联网公司属于科技吗 保山互联网科技靠谱吗 众联互联网络科技 知域互联网科技有限公司官网 利用互联网等科技手段 颐高云石互联网科技 深圳互联网络科技有限公司 狮子座互联网科技 互联网科技公司介绍 欧洲十大科技互联网公司 互联网科技创新服务 互联网金融科技名词解释 江苏互联网智能科技软件 科技互联网行业投资研究 互联网高科技行业有哪些企业 广州三三互联网科技有限公司

相关文章

0