门窗网站模板,常见的网站推广途径,可以看任何网站的浏览器下载,凡科网上传网站文章目录摘要描述题解答案题解代码分析代码解析示例测试及结果输出结果时间复杂度空间复杂度总结摘要
在开发中#xff0c;我们经常遇到需要处理大规模有序数据的场景#xff0c;比如数据库分页、排行榜查询、或者处理排序过的矩阵。LeetCode 第 378 题“有序矩阵中第 K 小的… 文章目录摘要描述题解答案题解代码分析代码解析示例测试及结果输出结果时间复杂度空间复杂度总结摘要
在开发中我们经常遇到需要处理大规模有序数据的场景比如数据库分页、排行榜查询、或者处理排序过的矩阵。LeetCode 第 378 题“有序矩阵中第 K 小的元素”就是这样一个经典问题它要求我们在一个行列都排好序的矩阵中快速找到第 K 小的元素。本文将结合代码、算法思路和实际场景带大家拆解这个题目的解法。 描述
题目要求我们在一个 n × n 的有序矩阵 中找到第 K 小的元素。矩阵的特点是
每一行是按升序排列的每一列也是按升序排列的。
换句话说矩阵不仅仅是二维数组它在行和列两个维度上都保持有序。 我们需要返回排序后第 K 小的那个元素而不是第 K 个不同的元素。
比如
输入matrix [[1,5,9],[10,11,13],[12,13,15]], k 8
输出13
解释矩阵展开后是 [1,5,9,10,11,12,13,13,15]第 8 小的数是 13这个问题在实际开发中也很常见比如
在数据库表中进行多字段排序后查找某个偏移量的数据在分布式日志系统中根据时间和序号找到某条具体日志在推荐系统里找到用户兴趣排序中的第 K 个候选项。
题解答案
针对这个问题有几个常见的思路 最直接的做法把矩阵“扁平化”拉成一个数组然后排序再取第 K 个。 时间复杂度O(n² log n²)太大。空间复杂度O(n²)内存开销也大。 利用小顶堆最小堆每一行都是有序的所以我们可以把每行的第一个元素丢进最小堆每次弹出最小值再把该元素所在行的下一个元素压入堆。这样循环 K 次就能得到第 K 小的元素。 时间复杂度O(k log n)。 二分查找 计数利用矩阵整体有序的性质在数值范围内进行二分搜索统计小于等于 mid 的元素个数。根据计数结果收缩区间直到找到第 K 小的数。 时间复杂度O(n log(max-min))比堆解法更节省内存。
这里我们选择 二分查找的解法因为它更高效也符合题目“内存复杂度优于 O(n²)”的要求。 题解代码分析
下面是 Swift 的实现代码使用二分查找
import Foundationclass Solution {func kthSmallest(_ matrix: [[Int]], _ k: Int) - Int {let n matrix.countvar left matrix[0][0]var right matrix[n - 1][n - 1]func countLessEqual(_ mid: Int) - Int {var count 0var row n - 1var col 0// 从左下角开始统计 mid 的元素个数while row 0 col n {if matrix[row][col] mid {count row 1col 1} else {row - 1}}return count}// 二分查找while left right {let mid left (right - left) / 2if countLessEqual(mid) k {left mid 1} else {right mid}}return left}
}代码解析 left 和 right 分别是矩阵中的最小值和最大值作为二分查找的边界。 countLessEqual(mid) 用来统计矩阵中小于等于 mid 的元素个数。这里从 左下角 开始走效率高。 如果当前元素 ≤ mid那么这一列到当前行的所有数都 ≤ mid所以 count row 1。如果当前元素 mid就往上一行走。 在二分查找过程中如果统计结果 k说明 mid 太小需要右移否则收缩右边界。 最终 left 就是第 K 小的数。
示例测试及结果
let solution Solution()let matrix1 [[1,5,9],[10,11,13],[12,13,15]]
print(solution.kthSmallest(matrix1, 8))
// 输出: 13let matrix2 [[-5]]
print(solution.kthSmallest(matrix2, 1))
// 输出: -5输出结果
13
-5这和题目示例完全一致说明算法是正确的。
时间复杂度
二分查找在区间 [min, max] 上进行区间大小是数值范围复杂度是 O(log(max-min))。 每次统计时需要遍历一行或一列总共 O(n)。 因此总体复杂度是 O(n log(max-min))
对于 n 300 的规模这个复杂度是可以接受的。
空间复杂度
整个算法只使用了几个变量没有额外的存储结构空间复杂度是 O(1)
相比直接展开矩阵存储节省了大量内存非常适合大规模数据。
总结
这道题考察的关键点在于 如何利用矩阵的有序性。
如果直接暴力排序肯定超时或内存爆炸。用堆可以解决但还是会有 O(n) 的额外存储。最优解是二分查找 计数既利用了矩阵的有序性又避免了额外存储。
在实际业务中这个思路同样适用
处理数据库分页查询时可以用“数值二分 索引统计”来代替大规模排序。在大规模日志或指标矩阵中查找排名时也可以用这个思路快速定位。
所以这道题不仅是算法练习更是一种 高效思维方式 的锻炼。
