DeepSeek LeetCode 1439. 有序矩阵中的第 k 个最小数组和 public int kthSmallest(int[][] mat, int k)

这道题是1434的下一题要求从矩阵的每一行选一个数得到数组和找出第 k 小的和。核心思路多路归并 最小堆第一行每个数作为初始和依次合并下一行当前所有和 新行的每个元素用最小堆维护前 k 小的和代码实现 ACclassSolution{publicintkthSmallest(int[][]mat,intk){intmmat.length;// 行数intnmat[0].length;// 列数// 第一行的所有数作为初始候选和PriorityQueueIntegerpqnewPriorityQueue();for(intnum:mat[0]){pq.offer(num);}// 依次合并后续每一行for(introw1;rowm;row){PriorityQueueIntegernextPqnewPriorityQueue();// 当前所有候选和 新行的每个元素while(!pq.isEmpty()){intcurrSumpq.poll();for(intnum:mat[row]){nextPq.offer(currSumnum);}}// 只保留前 k 个最小的for(inti0;ik!nextPq.isEmpty();i){pq.offer(nextPq.poll());}}// 第 k 个最小的在堆顶因为最后只剩 k 个intresult0;for(inti0;ik;i){resultpq.poll();}returnresult;}}复杂度分析时间复杂度O(m × n × k × log k)空间复杂度O(k)更优解法二分答案由于 k 可能很大最多 200上述方法在 k 接近 n^m 时会超时可以用二分 计数优化classSolution{publicintkthSmallest(int[][]mat,intk){intmmat.length;intleft0,right0;// 最小和每行第一个数之和for(inti0;im;i){leftmat[i][0];rightmat[i][n-1];}intbaseleft;// 基准和最小和// 二分查找第 k 小的数组和while(leftright){intmidleft(right-left)/2;// 统计有多少种数组和 midintcountcountArraysSumLessThan(mat,0,mid,base,k);if(countk){rightmid;}else{leftmid1;}}returnleft;}privateintcountArraysSumLessThan(int[][]mat,introw,inttarget,intsum,intk){if(rowmat.length)return1;if(sumtarget)return0;intcount0;for(intval:mat[row]){countcountArraysSumLessThan(mat,row1,target,sumval,k);if(countk)break;// 剪枝}returncount;}}两种方法对比方法优点缺点多路归并简单直观容易实现k 大时可能超时二分计数效率更高适合大数据实现稍复杂关键点初始堆用第一行所有数每合并一行只保留前 k 个最小和最后堆顶就是第 k 个如果用堆弹出 k 次