查找第 K 个最小对距离

2024-08-15 0 182

查找第 K 个最小对距离

719。找到第 k 个最小的对距离

难度: 难

主题: 数组、两个指针、二分查找、排序

整数对距离定义为a和b之间的绝对差。

给定一个整数数组 nums 和一个整数 k,返回所有对 nums[i] 和 nums[j] 中最小的距离,其中 0 .

示例1:

    输入:

  • nums = [1,3,1], k = 1
  • 输出:

  • 0
  • 说明

  • 这是所有的对:

    1

    2

    3

    (1,3) -> 2

    (1,1) -> 0

    (3,1) -> 2

  • 那么第1

st

最小距离对是(1,1),它的距离是0.

示例2:

    输入:

  • nums = [1,1,1], k = 2
  • 输出:

  • 0

示例3:

    输入:

  • nums = [1,6,1], k = 3
  • 输出:

  • 5

限制:

n == nums.length

  • 2 4
  • 0 6
  • 1

提示:

二分查找答案。如何检查有多少对具有距离

解决方案:

我们可以结合使用二分查找和双指针技术。这是解决此问题的分步方法:

方法:

  1. 对数组进行排序

    :首先,对数组 nums 进行排序。排序有助于有效计算距离小于或等于给定值的对的数量。

  2. 距离二分查找

    :使用二分查找找到第 k 个最小距离。距离的搜索空间范围从 0(最小可能距离)到 max(nums) – min(nums)(最大可能距离)。

  3. 计数距离 ≤ mid 的对

    :对于二分查找中的每个 mid 值,计算距离小于或等于 mid 的对的数量。这可以使用两指针方法有效地完成。

  4. 调整二分查找范围

    :根据距离小于或等于mid的对的数量,调整二分查找范围。如果计数小于k,则增加下界;否则,减小上限。

  5. 让我们用 php 实现这个解决方案:

719。找到第 k 个最小对距离

解释:

  • countpairswithdistancelessthanorequalto

    :此函数计算有多少对距离小于或等于 mid。它使用两个指针,其中right是当前元素,left调整直到nums[right]和nums[left]之间的差小于或等于mid。

  • smallestdistancepair

    :该函数使用二分查找来查找第 k 个最小距离。低值和高值定义距离的当前搜索范围。使用 countpairswithdistancelessthanorequalto 函数检查中间值。根据结果​​调整搜索空间。

  • 该算法有效地找到第 k 个最小对距离,时间复杂度为 o(n log(max(nums) – min(nums)) + n log n)。

联系链接

如果您发现本系列有帮助,请考虑在 Github 上给存储库

收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信/支付宝扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

免责声明
1. 本站所有资源来源于用户上传和网络等,如有侵权请邮件联系本站整改team@lcwl.fun!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系本站工作人员处理!
6. 本站资源售价或VIP只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!
8. 因人力时间成本问题,部分源码未能详细测试(解密),不能分辨部分源码是病毒还是误报,所以没有进行任何修改,大家使用前请进行甄别!
9.本站所有源码资源都是经过本站工作人员人工亲测可搭建的,保证每个源码都可以正常搭建,但不保证源码内功能都完全可用,源码属于可复制的产品,无任何理由退款!

网站搭建学习网 PHP 查找第 K 个最小对距离 https://www.xuezuoweb.com/13201.html

常见问题
  • 本站所有的源码都是经过平台人工部署搭建测试过可用的
查看详情
  • 购买源码资源时购买了带主机的套餐是指可以享受源码和所选套餐型号的主机两个产品,在本站套餐里开通主机可享优惠,最高免费使用主机
查看详情

相关文章

发表评论
暂无评论
官方客服团队

为您解决烦忧 - 24小时在线 专业服务

Fa快捷助手
手机编程软件开发

在手机上用手点一点就能轻松做软件

去做软件
链未云主机
免备案香港云主机

开通主机就送域名的免备案香港云主机

去使用
链未云服务器
免备案香港云服务器

支持售后、超低价、稳定的免备案香港云服务器

去使用