文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 为什么这是“二分答案”的题
- 统计 ≤ mid 的元素个数
- Swift 可运行 Demo 代码
- 代码拆解说明
- 1. 为什么 `left` 和 `right` 这样初始化
- 2. `count < k` 为什么要 `left = mid + 1`
- 3. 为什么最后直接返回 `left`
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结
摘要
LeetCode 378「有序矩阵中第 K 小的元素」是一道非常容易被写“重”的题。
很多人第一反应是：
既然矩阵是有序的，那我全部摊平成数组，再排序不就好了？
没错，能过，但空间复杂度直接炸到 O(n²)，而题目明确告诉你：
你必须用更省内存的方式。
这道题真正考的不是排序，而是你有没有意识到：
“答案本身也是有序的，可以用二分去猜。”
这篇文章会重点讲清楚：
- 为什么这是一个“对值域做二分”的问题
- 为什么不需要真的把第 k 个元素找出来
- Swift 下如何写出一个稳定、易读的实现
描述
题目给你一个 n x n 的矩阵 matrix，并保证：
- 每一行是升序
- 每一列也是升序
注意这里有一个很重要的点：
它不是整体排序后的第 k 个“不同元素”，
而是 排序后的位置第 k 个元素。
比如：
[1,5,9,10,11,13,12,13,15]展开后是：
[1,5,9,10,11,12,13,13,15]第 8 个元素是 13，而不是跳过重复。
题解答案
这道题最主流、也最稳妥的解法是：
对值域做二分查找 + 利用矩阵有序性统计 ≤ mid 的元素个数
核心思路一句话总结：
- 矩阵是有序的
- 第 k 小的值，一定在
[最小值, 最大值]这个区间里 - 我们不关心它在哪，只关心 “小于等于某个值的数有多少个”
题解代码分析
为什么这是“二分答案”的题
很多人卡在一个误区里：
二分不是只能用在数组索引上吗？
其实不是。
只要答案满足单调性，就能二分。
在这道题中：
值越小
- ≤ 这个值的元素数量越少
值越大
- ≤ 这个值的元素数量越多
这是一个天然的单调关系。
统计 ≤ mid 的元素个数
这是整道题最关键的地方。
因为矩阵行列都有序，我们可以这样做：
从 左下角 开始
如果当前值 ≤ mid
- 说明这一列上面的都 ≤ mid
- 一次性加一整列
如果当前值 > mid
- 往上移动
这个过程是 O(n) 的。
Swift 可运行 Demo 代码
class Solution {
func kthSmallest(_ matrix: [[Int]], _ k: Int) -> Int {
let n = matrix.count
var left = matrix[0][0]
var right = matrix[n - 1][n - 1]
while left < right {
let mid = left + (right - left) / 2
let count = countLessOrEqual(matrix, mid)
if count < k {
left = mid + 1
} else {
right = mid
}
}
return left
}
private func countLessOrEqual(_ matrix: [[Int]], _ target: Int) -> Int {
let n = matrix.count
var row = n - 1
var col = 0
var count = 0
while row >= 0 && col < n {
if matrix[row][col] <= target {
count += row + 1
col += 1
} else {
row -= 1
}
}
return count
}
}代码拆解说明
1. 为什么 left 和 right 这样初始化
var left = matrix[0][0]
var right = matrix[n - 1][n - 1]因为：
- 矩阵整体是有序的
- 左上角是最小值
- 右下角是最大值
这是值域的天然边界。
2. count < k 为什么要 left = mid + 1
这一步非常关键。
含义是：
- 当前
mid太小 - 小于等于
mid的元素还不够k个 - 第 k 小的数一定在右边
3. 为什么最后直接返回 left
因为循环结束条件是：
left == right而这个值，刚好是：
第一个满足“≤ 它的元素个数 ≥ k”的数
也就是第 k 小的元素。
示例测试及结果
let solution = Solution()
print(solution.kthSmallest([[1,5,9],[10,11,13],[12,13,15]], 8))
// 13
print(solution.kthSmallest([[-5]], 1))
// -5输出结果：
13
-5时间复杂度
- 二分次数：
log(maxValue - minValue) - 每次统计：
O(n)
整体复杂度：
O(n * log(range))在 n <= 300 的限制下，非常安全。
空间复杂度
除了几个变量，没有额外数据结构：
O(1)完全满足题目的进阶要求。
总结
LeetCode 378 是一道非常适合用来训练“二分答案思维”的题：
- 不在数组上二分
- 而是在“可能的结果范围”上二分
这种思路在实际开发中也很常见，比如：
- 资源分配的最小可行值
- 系统阈值调优
- 延迟、吞吐量的临界点搜索
如果你能把这道题讲清楚，
那你对“二分”的理解，已经明显高于只会套模板的人了。