# 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](/leetcode-solution/medium/240.search-a-2-d-matrix-ii.md)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 47K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/378.kth-smallest-element-in-a-sorted-matrix.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.