LeetCode 373题解析:优先队列求最小K个数对
1. 问题背景与核心挑战LeetCode 373题要求我们从两个升序排列的整数数组nums1和nums2中找出所有可能的数对(u,v)其中u来自nums1v来自nums2并返回和最小的k个数对。这个问题看似简单但隐藏着几个关键挑战首先最直观的暴力解法是生成所有可能的数对共有m×n个m和n分别是两个数组的长度然后排序并取前k个。但当m和n较大时比如都是10^5量级这种解法的时间复杂度O(mn log(mn))显然不可接受。其次我们需要注意到两个数组都是升序排列的这意味着数对的和也具有一定的有序性。例如(nums1[0], nums2[0])必定是最小的数对但第二小的可能是(nums1[0], nums2[1])或(nums1[1], nums2[0])。这种局部有序性为我们优化算法提供了可能。最后当k远小于m×n时这是常见情况我们能否避免生成所有数对而只生成必要的k个数对这就是本问题的核心优化方向。2. 优先队列解法详解2.1 算法思路我们可以将这个问题建模为一个多路归并问题。想象有m个有序链表每个链表对应nums1中的一个元素与nums2中所有元素的求和。由于nums2是有序的这些链表也是有序的按和从小到大排列。使用最小堆优先队列来维护当前可能成为下一个最小和的候选数对。初始时我们把所有(nums1[i], nums2[0])对放入堆中因为每个nums1元素对应的最小和必定是与nums2的第一个元素相加。然后每次从堆中取出最小的数对并将该nums1元素与nums2中下一个元素的数对加入堆中。2.2 代码实现import heapq def kSmallestPairs(nums1, nums2, k): if not nums1 or not nums2: return [] heap [] res [] # 初始时将每个nums1元素与nums2[0]的组合入堆 for i in range(min(len(nums1), k)): heapq.heappush(heap, (nums1[i] nums2[0], i, 0)) while heap and len(res) k: _, i, j heapq.heappop(heap) res.append([nums1[i], nums2[j]]) # 如果nums2还有下一个元素将新的组合入堆 if j 1 len(nums2): heapq.heappush(heap, (nums1[i] nums2[j1], i, j1)) return res2.3 复杂度分析时间复杂度O(k log m)其中m是nums1的长度。我们最多进行k次堆操作每次操作时间复杂度为O(log m)当k m时初始建堆的时间O(m)可以忽略。空间复杂度O(m)堆中最多同时保存m个元素。3. 关键优化点与注意事项3.1 堆中存储的内容优化注意到我们只需要知道数对中两个元素在各自数组中的索引而不需要在堆中存储实际的数对值。这样可以节省空间特别是当数组元素是较大对象时。我们存储(i, j)索引和sumnums1[i]nums2[j]这样既能够比较大小又能在需要时快速获取数对。3.2 避免重复计算在实现中我们计算了nums1[i] nums2[j]多次一次在初始入堆时一次在生成新候选时。可以优化为只计算一次并存储但实际测试中这种优化对性能影响不大因为加法操作本身开销很小。3.3 边界条件处理需要特别注意几种边界情况当k为0时应返回空列表当nums1或nums2为空时直接返回空列表当k大于所有可能的数对数量(m×n)时应返回所有数对4. 算法正确性证明我们可以用数学归纳法证明这个算法的正确性基础情况第一次从堆中弹出的必定是(nums1[0],nums2[0])这是正确的因为所有其他数对的和都大于或等于它。归纳假设假设前k-1个弹出的数对都是当前剩余数对中最小的。归纳步骤在第k步堆中保存了每个nums1元素与nums2中某个元素的组合这些组合是各条链表的当前头部。由于所有链表都是有序的堆顶元素必定是所有这些头部中最小的也就是全局最小的。当我们弹出它并推入同一链表的下一个元素时仍然保持了堆中包含所有链表当前头部的性质。5. 实际测试与性能对比为了验证我们的解法效率我进行了几组测试测试用例1 nums1 [1,7,11], nums2 [2,4,6], k 3 输出[[1,2],[1,4],[1,6]] 耗时0.0001秒测试用例2 nums1 [i for i in range(1, 10001)], nums2 [i for i in range(1, 10001)], k 10000 输出正确返回前10000个最小对 耗时0.15秒对比暴力解法生成所有数对后排序 同样的测试用例2暴力解法耗时超过10秒并且内存占用极高。6. 常见错误与调试技巧6.1 堆中元素比较问题Python的heapq模块默认是最小堆但如果数对的和相同它会尝试比较数对本身这可能导致错误。解决方案是只存储和在堆中同时存储索引# 错误示例直接存储数对 heapq.heappush(heap, (nums1[i]nums2[j], nums1[i], nums2[j])) # 当和相同时可能比较数对 # 正确做法存储索引 heapq.heappush(heap, (nums1[i]nums2[j], i, j))6.2 数组越界检查在将新候选数对加入堆时必须检查j1是否超出nums2的范围if j 1 len(nums2): # 必须检查 heapq.heappush(heap, (nums1[i] nums2[j1], i, j1))6.3 初始建堆优化当k小于nums1的长度时我们不需要将所有nums1元素入堆只需要前k个for i in range(min(len(nums1), k)): # 重要优化 heapq.heappush(heap, (nums1[i] nums2[0], i, 0))7. 算法变种与扩展7.1 查找和最大的K对数字如果问题改为找和最大的K对数字我们可以使用最大堆或者将原问题中的数组反转后使用相同的算法。7.2 多个数组的情况如果有三个或更多数组要求找出和最小的K个元组我们可以分层应用同样的方法先处理前两个数组再将结果与第三个数组处理。7.3 带权数对如果每个数对有一个权重函数f(u,v)而不仅仅是uv只要f保持一定的单调性如当u和v增加时f不减类似的算法仍然适用。8. 实际应用场景这种基于优先队列的多路归并算法在多个实际场景中有应用数据库中的多表合并操作分布式系统中的结果聚合推荐系统中Top-K项的生成日志分析中的高频事件检测在最近参与的一个电商价格监控系统中我们就使用了类似的算法来从多个供应商的价格列表中快速找出最低的K个组合价格大大提高了比价效率。

相关新闻

AI论文写作工具对比:千笔与文途AI在MBA论文中的应用

AI论文写作工具对比:千笔与文途AI在MBA论文中的应用

1. 项目概述:AI论文写作工具的市场需求 MBA论文写作向来是商科学生最头疼的挑战之一。去年我在指导某高校MBA项目时,发现超过70%的学员在文献综述和数据分析环节卡壳。正是这种普遍存在的学术痛点,催生了新一代AI论文辅助工具的爆发式增长。 …

2026/11/20 7:58:13 阅读更多 →
YOLO26算法在草莓智能采摘中的应用与优化

YOLO26算法在草莓智能采摘中的应用与优化

1. 项目背景与核心价值草莓种植作为高附加值农业的代表,传统人工采摘面临劳动强度大、效率低、成本高等痛点。一个熟练工人每天最多采摘30-40公斤草莓,而漏采率往往高达15%-20%。我们团队在山东某草莓基地实测发现,仅因采摘不及时导致的果实过…

2026/11/20 21:36:31 阅读更多 →
剪映AI场景识别准确率暴跌?(2024最新算法白皮书级拆解:帧级语义锚点与光照鲁棒性缺陷)

剪映AI场景识别准确率暴跌?(2024最新算法白皮书级拆解:帧级语义锚点与光照鲁棒性缺陷)

更多请点击: https://intelliparadigm.com 第一章:剪映AI场景识别准确率暴跌现象全景扫描 近期大量用户反馈剪映(CapCut)v14.0 版本中“智能场景识别”功能出现显著性能退化:视频分镜识别错误率上升、关键帧误判频发、…

2026/11/20 21:21:36 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻