力扣 373：有序数组最小K数对的暴力与优化双解

力扣 373有序数组最小K数对的暴力与优化双解 前言算法千般道有序为捷径Bilibili 同步视频 一、题意剖释明解题之本晓边界之规1.1 原题题意1.2 解题前置心法为何选用大顶堆 二、暴力枚举解法直白可行却逢时限之困2.1 算法思路Plain Text原理示意图2.2 完整C暴力源码2.3 致命缺陷与超时根源⚡ 三、有序特性优化顺势而为斩断无效遍历3.1 优化核心原理Plain Text分步图解3.2 优化前后性能直观对比3.3 完整版优化C代码可直接AC通过3.4 关键代码逐行注解 四、算法求学悟道万般阻碍皆为成长土壤 全文骈文速记口诀一键吃透本题 文末总结 前言算法千般道有序为捷径数组分列有序成行数对相依和值分章。刷题千万误区暗藏枚举全域虽稳难免超时之殇善用序列天性方可破壁图强。本篇以双有序数组寻找和最小K个数对为核心骈文行文、对仗释理逐层拆解暴力大顶堆解法、超时根源、有序特性极致优化方案附完整可运行C源码、分步原理图、性能对照分析由表及里由愚至巧吃透堆排序有序数组双重算法核心✨。Bilibili 同步视频力扣 373有序数组最小K数对的暴力与优化双解 一、题意剖释明解题之本晓边界之规1.1 原题题意给定两个升序排列的整数数组 nums1、nums2从两数组中分别取出一个元素组成数对要求返回所有数对中和值最小的前K个数对。约束核心元素一一配对一数取自nums1一数取自nums2数组全程升序元素从左至右单调递增输出结果无需再次排序保留堆筛选后的有效数对即可1.2 解题前置心法为何选用大顶堆求前K小堆分两类小顶堆逐次弹出最小值冗余遍历开销居高不下大顶堆留存备选集合堆顶为当前备选最大值超限则剔除大数留小去大适配本题最优场景✅。核心逻辑维护容量为K的大顶堆始终保留当前最小的K组数对新数对小于堆顶则入堆大于堆顶直接舍弃。 二、暴力枚举解法直白可行却逢时限之困2.1 算法思路Plain Text原理示意图【暴力枚举流程】 nums1: [1,2,4] nums2: [1,3,5] 全量两两枚举 → 生成全部9组数对 全部入大顶堆 → 堆容量超过K → 弹出堆顶最大值 最终剩余K组最小数对 缺陷无视数组有序性无脑全遍历数据量大直接TLE2.2 完整C暴力源码#includeiostream#includevector#includequeueusingnamespacestd;// 自定义比较器构建大顶堆按照数对之和降序排列structcmp{booloperator()(vectorinta,vectorintb){returna[0]a[1]b[0]b[1];}};vectorvectorintkSmallestPairs(vectorintnums1,vectorintnums2,intk){// 定义大顶堆priority_queuevectorint,vectorvectorint,cmpmaxHeap;// 双层循环无脑枚举所有数对for(intx:nums1){for(inty:nums2){maxHeap.push({x,y});// 堆容量超出K弹出当前最大数对if(maxHeap.size()k){maxHeap.pop();}}}// 导出结果vectorvectorintres;while(!maxHeap.empty()){res.push_back(maxHeap.top());maxHeap.pop();}returnres;}intmain(){vectorintn1{1,2,4};vectorintn2{1,3,5};autoanskSmallestPairs(n1,n2,3);for(autoitem:ans){coutitem[0] item[1]endl;}return0;}2.3 致命缺陷与超时根源双循环嵌套全域遍历所有组合时间复杂度高达O(N*M)。两数组皆为升序序列代码完全舍弃有序天性后续递增数对无需校验依旧强行入堆无效计算堆砌大数据场景直接触发TLE超时错误。痛点总结算法切忌蛮力遍历无视题干特性直白代码终究难抗大数据评测用例。⚡ 三、有序特性优化顺势而为斩断无效遍历3.1 优化核心原理Plain Text分步图解【有序数组优化逻辑】 已知nums1、nums2 全局升序 固定 nums1 中元素 x向后遍历 nums2 nums2 元素y持续变大 → xy 和值持续单调递增 判定规则 1. 堆未满k个直接入堆无需判断 2. 堆已满k个当前和 堆顶和 → 替换堆顶 3. 当前和 ≥ 堆顶和 → 后续所有和只会更大 → 直接break终止内层循环 核心依托单调性提前截断循环消灭全部无效遍历3.2 优化前后性能直观对比解法类型时间复杂度运行耗时是否超时暴力全枚举O(N*M)130ms是有序截断优化O(N*K)12ms左右否3.3 完整版优化C代码可直接AC通过#includeiostream#includevector#includequeueusingnamespacestd;structcmp{booloperator()(vectorinta,vectorintb){returna[0]a[1]b[0]b[1];}};vectorvectorintkSmallestPairs(vectorintnums1,vectorintnums2,intk){priority_queuevectorint,vectorvectorint,cmpmaxHeap;for(intx:nums1){for(inty:nums2){intcurSumxy;// 分支1堆内元素不足k直接存入if(maxHeap.size()k){maxHeap.push({x,y});}else{// 分支2堆已满当前数对更小则替换堆顶if(curSummaxHeap.top()[0]maxHeap.top()[1]){maxHeap.pop();maxHeap.push({x,y});}else{// 依托升序单调性后续和值只会更大直接截断内层循环break;}}}}vectorvectorintres;while(!maxHeap.empty()){res.push_back(maxHeap.top());maxHeap.pop();}returnres;}intmain(){vectorintn1{1,2,4};vectorintn2{1,3,5};autoanskSmallestPairs(n1,n2,3);for(autoitem:ans){coutitem[0]item[1]item[0]item[1]endl;}return0;}3.4 关键代码逐行注解堆容量判断前置优先判断堆空间未满直接存入省去多余比较开销break截断核心内层循环一旦命中大于等于堆顶立刻终止本轮nums2遍历杜绝无效循环比较器无需深究数组比较依据为元素之和底层语法实现属于语言细节无需纠结底层重载逻辑聚焦算法思维即可 四、算法求学悟道万般阻碍皆为成长土壤刷题之路荆棘相伴代码之途苦练为岸。常有学子观他人代码行云流水自敲代码寸步难行妄图跳过实操一步登天此乃虚妄之念。天下代码无捷径可走一身功力唯苦练可成。天赋分高下努力无偏颇付出几分耕耘便得几分收获。遇难题而退缩困当下之桎梏迎难题而攻坚铺来日之坦途。譬如种子埋于泥土泥土一时为阻隔压制破土锋芒待到嫩芽而出泥土便为根基托举枝干生长。当下算法之难、代码之苦皆是脚下土壤今日熬过万般阻碍来日便可傲视群雄自成锋芒✨。 全文骈文速记口诀一键吃透本题双序数组寻小数大顶堆存备选组暴力双层全遍历无视序列超时苦升序单调和递增遇大截断少往复算法巧用题干性少算一步快一步刷题不惧当下苦困境终成脚下土。 文末总结本题看似是堆结构基础应用题实则考察算法优化思维优秀的代码从不是无脑模拟流程而是读懂题干隐藏条件顺势简化计算。暴力解法保正确率优化解法保运行效率二者结合方能兼顾逻辑与性能。 评论区交流你刷题时是否也经常无脑遍历忽略数组有序特性欢迎留言讨论#算法 #C #大顶堆 #数组算法 #LeetCode刷题 #代码优化