首页 后端开发 php教程 。 K 列表中的最小范围覆盖元素

。 K 列表中的最小范围覆盖元素

Oct 14, 2024 am 06:23 AM

. Smallest Range Covering Elements from K Lists

632。 K 个列表中的最小范围覆盖元素

难度:

主题:数组、哈希表、贪婪、滑动窗口、排序、堆(优先级队列)

你有 k 个按 非递减顺序排序的整数列表。查找 最小 范围,其中至少包含 k 个列表中每个列表中的一个数字。

如果 b - a 或 a

c 如果 b - a == d - c。

示例1:

  • 输入:
  • nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
  • 输出:
  • [20,24]
  • 说明:
    • 列表 1:[4, 10, 15, 24,26],24 在范围 [20,24] 内。
    • 列表 2:[0, 9, 12, 20],20 在范围 [20,24] 内。
    • 列表 3:[5, 18, 22, 30],22 在范围 [20,24] 内。

示例2:

  • 输入:
  • nums = [[1,2,3],[1,2,3],[1,2,3]]
  • 输出:
  • [1,1]

约束:

  • nums.length == k
  • 1 1 -105 5
  • nums[i] 按非递减
  • 顺序排序。

解决方案:

我们可以使用 min-heap

(或优先级队列)来跟踪每个列表中的最小元素,同时维护一个滑动窗口来查找包含每个列表中至少一个元素的最小范围。

方法
  1. 最小堆初始化
  2. :使用最小堆来存储 k 个列表中每个列表中的当前元素。每个堆条目都是一个元组,其中包含值、它来自的列表的索引以及该列表中元素的索引。
  3. 最大值跟踪
  4. :跟踪当前窗口中的最大值。这很重要,因为范围是由最小元素(来自堆)和当前最大值之间的差异决定的。
  5. 迭代直到列表末尾
      :对于每次迭代:
    • 从堆中提取最小元素。
    • 如果当前范围[min_value, max_value]小于之前记录的最小范围,则更新范围。
    • 移至列表中从中获取最小元素的下一个元素。更新最大值并将新元素添加到堆中。
  6. 终止
  7. :当任何列表耗尽时,进程结束。

让我们用 PHP 实现这个解决方案:632。 K 列表中的最小范围覆盖元素

<?php
/**
 * @param Integer[][] $nums
 * @return Integer[]
 */
function smallestRange($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]];
$result = smallestRange($nums);
print_r($result); // Output: [20, 24]
?>
登录后复制

解释:
  1. 堆初始化
    • 初始堆包含每个列表中的第一个元素。我们还跟踪第一个元素中的最大元素。
  2. 处理堆
    • 从堆中提取最小元素,然后尝试通过添加同一列表中的下一个元素(如果可用)来扩展范围。
    • 向堆中添加新元素后,如果新元素更大,则更新 maxValue。
    • 每当 maxValue 和 minValue 之间的差值小于之前记录的范围时,更新最小范围。
  3. 终止
    • 当任何列表用完元素时循环就会停止,因为我们不能再包含该范围内的所有列表。

复杂性分析
  • 时间复杂度
  • :O(n * log k),其中n是所有列表中的元素总数,k是列表的数量。复杂性来自于在堆中插入和删除元素。
  • 空间复杂度
  • :在堆中存储元素的O(k)。

该解决方案有效地找到包含 k 个排序列表中每个列表中至少一个数字的最小范围。

联系链接

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

一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!

如果您想要更多类似的有用内容,请随时关注我:
  • 领英
  • GitHub

以上是。 K 列表中的最小范围覆盖元素的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

<🎜>:泡泡胶模拟器无穷大 - 如何获取和使用皇家钥匙
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系统,解释
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

热门话题

Java教程
1664
14
CakePHP 教程
1423
52
Laravel 教程
1321
25
PHP教程
1269
29
C# 教程
1249
24
PHP和Python:比较两种流行的编程语言 PHP和Python:比较两种流行的编程语言 Apr 14, 2025 am 12:13 AM

PHP和Python各有优势,选择依据项目需求。1.PHP适合web开发,尤其快速开发和维护网站。2.Python适用于数据科学、机器学习和人工智能,语法简洁,适合初学者。

说明PHP中的安全密码散列(例如,password_hash,password_verify)。为什么不使用MD5或SHA1? 说明PHP中的安全密码散列(例如,password_hash,password_verify)。为什么不使用MD5或SHA1? Apr 17, 2025 am 12:06 AM

在PHP中,应使用password_hash和password_verify函数实现安全的密码哈希处理,不应使用MD5或SHA1。1)password_hash生成包含盐值的哈希,增强安全性。2)password_verify验证密码,通过比较哈希值确保安全。3)MD5和SHA1易受攻击且缺乏盐值,不适合现代密码安全。

PHP行动:现实世界中的示例和应用程序 PHP行动:现实世界中的示例和应用程序 Apr 14, 2025 am 12:19 AM

PHP在电子商务、内容管理系统和API开发中广泛应用。1)电子商务:用于购物车功能和支付处理。2)内容管理系统:用于动态内容生成和用户管理。3)API开发:用于RESTfulAPI开发和API安全性。通过性能优化和最佳实践,PHP应用的效率和可维护性得以提升。

PHP:网络开发的关键语言 PHP:网络开发的关键语言 Apr 13, 2025 am 12:08 AM

PHP是一种广泛应用于服务器端的脚本语言,特别适合web开发。1.PHP可以嵌入HTML,处理HTTP请求和响应,支持多种数据库。2.PHP用于生成动态网页内容,处理表单数据,访问数据库等,具有强大的社区支持和开源资源。3.PHP是解释型语言,执行过程包括词法分析、语法分析、编译和执行。4.PHP可以与MySQL结合用于用户注册系统等高级应用。5.调试PHP时,可使用error_reporting()和var_dump()等函数。6.优化PHP代码可通过缓存机制、优化数据库查询和使用内置函数。7

PHP的持久相关性:它还活着吗? PHP的持久相关性:它还活着吗? Apr 14, 2025 am 12:12 AM

PHP仍然具有活力,其在现代编程领域中依然占据重要地位。1)PHP的简单易学和强大社区支持使其在Web开发中广泛应用;2)其灵活性和稳定性使其在处理Web表单、数据库操作和文件处理等方面表现出色;3)PHP不断进化和优化,适用于初学者和经验丰富的开发者。

PHP类型提示如何起作用,包括标量类型,返回类型,联合类型和无效类型? PHP类型提示如何起作用,包括标量类型,返回类型,联合类型和无效类型? Apr 17, 2025 am 12:25 AM

PHP类型提示提升代码质量和可读性。1)标量类型提示:自PHP7.0起,允许在函数参数中指定基本数据类型,如int、float等。2)返回类型提示:确保函数返回值类型的一致性。3)联合类型提示:自PHP8.0起,允许在函数参数或返回值中指定多个类型。4)可空类型提示:允许包含null值,处理可能返回空值的函数。

PHP与Python:了解差异 PHP与Python:了解差异 Apr 11, 2025 am 12:15 AM

PHP和Python各有优势,选择应基于项目需求。1.PHP适合web开发,语法简单,执行效率高。2.Python适用于数据科学和机器学习,语法简洁,库丰富。

PHP和Python:代码示例和比较 PHP和Python:代码示例和比较 Apr 15, 2025 am 12:07 AM

PHP和Python各有优劣,选择取决于项目需求和个人偏好。1.PHP适合快速开发和维护大型Web应用。2.Python在数据科学和机器学习领域占据主导地位。

See all articles