算法题目有m个排序好的数组从小到大排序且长度不等组成的一个二维数组请你找到最小的第 k 个数。Python 实现例如数组[[1, 3, 5], [7, 8, 9], [2, 4, 6]]k5。LeetCode 378. 有序矩阵中第 K 小的元素 扩展题目题目分析题意①全局无序②子数组有序给定m个各自升序排列的一维数组构成二维数组全局所有元素中找出第 k 小的数。示例[[1,3,5],[7,8,9],[2,4,6]]所有元素排序[1,2,3,4,5,6,7,8,9]k5 → 结果为 5。介绍三种解法从暴力到最优方法 1暴力合并排序最简单适合数据量小把所有数组摊平成一维整体排序取下标 k-1一行就能写完。缺点时间复杂度(O(Nlog N))N为总元素数大数据低效。defkth_smallest_brute(matrix,k):arr[]forrowinmatrix:arr.extend(row)arr.sort()returnarr[k-1]# 测试if__name____main__:data[[1,3,5],[7,8,9],[2,4,6]]print(kth_smallest_brute(data,5))# 输出 5方法 2最小堆优先队列经典多路归并核心思路多路有序数组归并用小顶堆每次弹出最小值弹出第 k 次即为答案。先把每个数组第一个元素入堆记录(值, 数组索引, 元素在数组内下标)循环弹出堆顶最小元素计数 1若计数 k 直接返回如果弹出元素所在数组还有下一个元素继续入堆复杂度(O(klog m))m 为数组个数k 不大时效率极高。说明需要用到Python自带的包heapq有取巧嫌疑。importheapqdefkth_smallest_heap(matrix,k):heap[]mlen(matrix)foriinrange(m):# 初始化堆每个数组第一个元素入堆valmatrix[i][0]heapq.heappush(heap,(val,i,0))cnt0whileheap:val,row_idx,elem_idxheapq.heappop(heap)cnt1ifcntk:returnvalifelem_idx1len(matrix[row_idx]):# 当前数组还有下一个元素则入堆next_valmatrix[row_idx][elem_idx1]heapq.heappush(heap,(next_val,row_idx,elem_idx1))if__name____main__:test_arr[[1,3,5],[7,8,9],[2,4,6]]print(kth_smallest_heap(test_arr,5))# 5方法 3二分查找最优解法推荐大数据量思路利用值域二分自己想到的方法最小值left 所有数组首元素最小值最大值 right 所有数组尾元素最大值mid (leftright)//2统计二维数组中≤mid 的元素总数countcount k说明答案在右半区间leftmid1count ≥k答案在左半区间rightmid最终 leftright 就是第 k 小数复杂度(O(m log S))S 为数值值域范围性能上限最高。importbisectdefkth_smallest_binary(matrix,k):# 确定二分上下界leftmin(row[0]forrowinmatrix)rightmax(row[-1]forrowinmatrix)defcount_less_or_equal(x):统计所有数组中 x 的元素个数每行有序二分加速total0forrowinmatrix:totalbisect.bisect_right(row,x)# bisect_right 返回插入点即小于等于x的数量returntotalwhileleftright:mid(leftright)//2cntcount_less_or_equal(mid)ifcntk:leftmid1else:rightmidreturnleftif__name____main__:arr[[1,3,5],[7,8,9],[2,4,6]]print(kth_smallest_binary(arr,5))# 5总结数据很小 → 暴力一行版面试常规、多路归并考点 → 堆解法海量数据、追求极致效率 → 值域二分法。利用值域二分常考题目扩展1分割数组最大值 LeetCode 410 【常考】classSolution:defsplitArray(self,nums:List[int],k:int)-int:defcheck(target):total,cnt0,1fornuminnums:# 验证分割iftotalnumtarget:cnt1# 符合条件 1totalnum# 重新开始else:totalnumreturncntk left,rightmax(nums),sum(nums)# 确定上下界whileleftright:mid(leftright)//2ifcheck(mid):# 遍历验证rightmid# 本身就可能是最优值 所以不能 -1else:leftmid1returnleftif__name____main__:soluSolution()nums,k[1,4,2,3,5],3print(solu.splitArray(nums,k))2爱吃香蕉的珂珂 LeetCode 875