# 0378. 有序矩阵中第 K 小的元素
### 题目地址(378. 有序矩阵中第 K 小的元素)
### 题目描述
```
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例：
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
提示：
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
```
### 前置知识
* 二分查找
* 堆
### 公司
* 阿里
* 腾讯
* 字节
### 思路
显然用大顶堆可以解决，时间复杂度 Klogn，其中 n 为矩阵中总的数字个数。但是这种做法没有利用题目中 sorted matrix 的特点（横向和纵向均有序），因此不是一种好的做法.
一个巧妙的方法是二分法，我们分别从第一个和最后一个向中间进行扫描，并且计算出中间的数值与数组中的进行比较，可以通过计算中间值在这个数组中排多少位，然后得到比中间值小的或者大的数字有多少个，然后与 k 进行比较，如果比 k 小则说明中间值太小了，则向后移动，否则向前移动。
这个题目的二分确实很难想，我们来一步一步解释。
最普通的二分法是有序数组中查找指定值（或者说满足某个条件的值）这种思路比较直接，但是对于这道题目是二维矩阵，而不是一维数组，因此这种二分思想就行不通了。
(普通的一维二分法)
而实际上：
* 我们能够找到矩阵中最大的元素（右下角）和最小的元素（左上角）。接下来我们可以求出**值的中间**，而不是上面那种普通二分法的索引的中间。
* 找到中间值之后，我们可以拿这个值去计算有多少元素是小于等于它的。具体方式就是比较行的最后一列，如果中间值比最后一列大，说明中间元素肯定大于这一行的所有元素。 否则我们从后往前遍历直到不大于。
* 上一步我们会计算一个 count，我们拿这个 count 和 k 进行比较
* 如果 count 小于 k，说明我们选择的中间值太小了，肯定不符合条件，我们需要调整左区间为 mid + 1
* 如果 count 大于 k，说明我们选择的中间值正好或者太大了。我们调整右区间 mid
> 由于 count 大于 k 也可能我们选择的值是正好的， 因此这里不能调整为 mid - 1， 否则可能会得不到结果
* 最后直接返回 start, end, 或者 mid 都可以，因此三者最终会收敛到矩阵中的一个元素，这个元素也正是我们要找的元素。
关于如何计算 count，我们可以从左下或者右上角开始，每次移动一个单位，直到找到一个值大于等于中间值，然后计算出 count，具体见下方代码。
整个计算过程是这样的：
这里有一个大家普遍都比较疑惑的点，就是“能够确保最终我们找到的元素一定在矩阵中么？”
答案是可以, **因为我们可以使用最左二分，这样假设我们找到的元素不在矩阵，那么我们一定可以找到比它小的在矩阵中的值，这和我们的假设（最左二分）矛盾**。
不懂最左二分请看我的二分专题。
### 关键点解析
* 二分查找
* 有序矩阵的套路（文章末尾还有一道有序矩阵的题目）
* 堆（优先级队列）
### 代码
代码支持：JS，Python3，CPP
JS：
```js
/*
* @lc app=leetcode id=378 lang=javascript
*
* [378] Kth Smallest Element in a Sorted Matrix
*/
function notGreaterCount(matrix, target) {
// 等价于在matrix 中搜索mid，搜索的过程中利用有序的性质记录比mid小的元素个数
// 我们选择左下角，作为开始元素
let curRow = 0;
// 多少列
const COL_COUNT = matrix[0].length;
// 最后一列的索引
const LAST_COL = COL_COUNT - 1;
let res = 0;
while (curRow < matrix.length) {
// 比较最后一列的数据和target的大小
if (matrix[curRow][LAST_COL] < target) {
res += COL_COUNT;
} else {
let i = COL_COUNT - 1;
while (i < COL_COUNT && matrix[curRow][i] > target) {
i--;
}
// 注意这里要加1
res += i + 1;
}
curRow++;
}
return res;
}
/**
* @param {number[][]} matrix
* @param {number} k
* @return {number}
*/
var kthSmallest = function (matrix, k) {
if (matrix.length < 1) return null;
let start = matrix[0][0];
let end = matrix[matrix.length - 1][matrix[0].length - 1];
while (start < end) {
const mid = start + ((end - start) >> 1);
const count = notGreaterCount(matrix, mid);
if (count < k) start = mid + 1;
else end = mid;
}
// 返回start,mid, end 都一样
return start;
};
```
Python3：
```python
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
def check(mid):
row, col = n - 1, 0
num = 0
while row >= 0 and col < n:
# 增加 col
if matrix[row][col] <= mid:
num += row + 1
col += 1
# 减少 row
else:
row -= 1
return num >= k
left, right = matrix[0][0], matrix[-1][-1]
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return left
```
CPP Code:
```cpp
class Solution {
public:
bool check(vector>& matrix, int mid, int k, int n) {
int row = n - 1;
int col = 0;
int num = 0;
while (row >= 0 && col < n) {
if (matrix[row][col] <= mid) {
num += i + 1;
col++;
} else {
row--;
}
}
return num >= k;
}
int kthSmallest(vector>& matrix, int k) {
int n = matrix.size();
int left = matrix[0][0];
int right = matrix[n - 1][n - 1];
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(matrix, mid, k, n)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
};
```
**复杂度分析**
* 时间复杂度：二分查找进行次数为 $O(log(r-l))$，每次操作时间复杂度为 O(n)，因此总的时间复杂度为 $O(nlog(r-l))$。
* 空间复杂度：$O(1)$。
### 相关题目
* [240.search-a-2-d-matrix-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/240.search-a-2-d-matrix-ii)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 47K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 