news 2026/7/7 2:12:37

LeetCode 373.查找和最小的K对数字

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
LeetCode 373.查找和最小的K对数字

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [[1,2],[1,4],[1,6]]
解释: 返回序列中的前 3 对数:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [[1,1],[1,1]]
解释: 返回序列中的前 2 对数:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

提示:

1 <= nums1.length, nums2.length <= 105^55
-109^99<= nums1[i], nums2[i] <= 109^99
nums1 和 nums2 均为 升序排列
1 <= k <= 104^44
k <= nums1.length * nums2.length

对于示例1,我们可以把所有可能的和看成一个矩阵:

其中每行都是非递减的,我们可以将其当作合并K个有序链表那样,每行的最小元素都放到堆里来处理:

classSolution{public:vector<vector<int>>kSmallestPairs(vector<int>&nums1,vector<int>&nums2,intk){vector<tuple<int,int,int>>h(nums1.size());for(inti=0;i<nums1.size();++i){h[i]={nums1[i]+nums2[0],i,0};}make_heap(h.begin(),h.end(),greater());vector<vector<int>>ans;ans.reserve(k);for(inti=0;i<k;++i){auto[_,idx1,idx2]=h[0];ans.push_back({nums1[idx1],nums2[idx2]});pop_heap(h.begin(),h.end(),greater());if(idx2<nums2.size()-1){h.back()={nums1[idx1]+nums2[idx2+1],idx1,idx2+1};push_heap(h.begin(),h.end(),greater());}else{h.pop_back();}}returnans;}};

如果nums1的长度为n,则此算法时间复杂度为O(n + klogn),空间复杂度为O(n)。

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/7/7 2:08:34

5分钟搞定VLC播放器终极美化:VeLoCity皮肤完整指南

5分钟搞定VLC播放器终极美化&#xff1a;VeLoCity皮肤完整指南 【免费下载链接】VeLoCity-Skin-for-VLC Castom skin for VLC Player 项目地址: https://gitcode.com/gh_mirrors/ve/VeLoCity-Skin-for-VLC 厌倦了VLC播放器千篇一律的默认界面&#xff1f;想要一个既美观…

作者头像 李华
网站建设 2026/7/7 2:07:28

BPF工具实战:中断、SMP调用与缓存性能

1. 中断时间分析&#xff1a;softirqs 和 hardirqs CPU在执行任务时&#xff0c;会花费一部分时间处理中断。传统工具如 mpstat 可以显示 CPU 在硬中断&#xff08;%irq&#xff09;和软中断&#xff08;%soft&#xff09;上的时间&#xff0c;但无法分解到具体的中断类型。BPF…

作者头像 李华
网站建设 2026/7/7 2:06:32

[特殊字符]遗忘之海PC公测|UU远程云电脑免费体验

终于等到遗忘之海PC公测上线✨&#xff01;整理了玩法亮点、开服福利和超好用的远程游玩技巧&#xff0c;新手开荒直接抄作业&#xff01;本次公测仅开放PC端口&#xff0c;很多宝子出门在外没法守着电脑&#xff0c;特别容易错过绝版福利和开荒进度&#x1f62d;&#xff01;还…

作者头像 李华
网站建设 2026/7/7 2:05:00

面包板 300mil 间距转接方案:3种 DIY 方法实测与成品对比

面包板 300mil 间距转接方案&#xff1a;3种 DIY 方法实测与成品对比在电子原型开发中&#xff0c;面包板因其免焊接、可重复使用的特性成为硬件调试的必备工具。但当我们面对双列直插&#xff08;DIP&#xff09;封装的模块时&#xff0c;标准面包板300mil&#xff08;7.62mm&…

作者头像 李华
网站建设 2026/7/7 2:04:48

鸿蒙 PC 底层开发技术详解(七):二进制自签名算法的实现

提示&#xff1a;本文创作过程中大量使用 AI 辅助研究&#xff0c;作者已验证代码结果的正确性&#xff0c;但无法保证所有结论一定严谨&#xff0c;切勿将文中结论用于严谨学术用途。 1 前言 本文是《鸿蒙 PC 底层开发技术详解&#xff08;四&#xff09;&#xff1a;代码签名…

作者头像 李华