LeetCode 378 有序矩阵中第 K 小的元素

摘要

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 代码

classSolution{funckthSmallest(_matrix:[[Int]],_k:Int)->Int{letn=matrix.countvarleft=matrix[0][0]varright=matrix[n-1][n-1]whileleft<right{letmid=left+(right-left)/2letcount=countLessOrEqual(matrix,mid)ifcount<k{left=mid+1}else{right=mid}}returnleft}privatefunccountLessOrEqual(_matrix:[[Int]],_target:Int)->Int{letn=matrix.countvarrow=n-1varcol=0varcount=0whilerow>=0&&col<n{ifmatrix[row][col]<=target{count+=row+1col+=1}else{row-=1}}returncount}}

代码拆解说明

1. 为什么left和right这样初始化

varleft=matrix[0][0]varright=matrix[n-1][n-1]

因为：

• 矩阵整体是有序的
• 左上角是最小值
• 右下角是最大值

这是值域的天然边界。

2.count < k为什么要left = mid + 1

这一步非常关键。

含义是：

• 当前mid太小
• 小于等于mid的元素还不够k个
• 第 k 小的数一定在右边

3. 为什么最后直接返回left

因为循环结束条件是：

left==right

而这个值，刚好是：

第一个满足“≤ 它的元素个数 ≥ k”的数

也就是第 k 小的元素。

示例测试及结果

letsolution=Solution()print(solution.kthSmallest([[1,5,9],[10,11,13],[12,13,15]],8))// 13print(solution.kthSmallest([[-5]],1))// -5

输出结果：

13 -5

时间复杂度

• 二分次数：log(maxValue - minValue)
• 每次统计：O(n)

整体复杂度：

O(n * log(range))

在n <= 300的限制下，非常安全。

空间复杂度

除了几个变量，没有额外数据结构：

O(1)

完全满足题目的进阶要求。

总结

LeetCode 378 是一道非常适合用来训练“二分答案思维”的题：

• 不在数组上二分
• 而是在“可能的结果范围”上二分

这种思路在实际开发中也很常见，比如：

• 资源分配的最小可行值
• 系统阈值调优
• 延迟、吞吐量的临界点搜索

如果你能把这道题讲清楚，
那你对“二分”的理解，已经明显高于只会套模板的人了。