第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0378. 有序矩阵中第 K 小的元素

题目地址(378. 有序矩阵中第 K 小的元素)

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

题目描述

1
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
2
请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。
3
4
5
6
示例:
7
8
matrix = [
9
[ 1, 5, 9],
10
[10, 11, 13],
11
[12, 13, 15]
12
],
13
k = 8,
14
15
返回 13。
16
17
18
提示:
19
你可以假设 k 的值永远是有效的,1 ≤ k ≤ n2 。
Copied!

前置知识

  • 二分查找

公司

  • 阿里
  • 腾讯
  • 字节

思路

显然用大顶堆可以解决,时间复杂度 Klogn,其中 n 为矩阵中总的数字个数。但是这种做法没有利用题目中 sorted matrix 的特点(横向和纵向均有序),因此不是一种好的做法.
一个巧妙的方法是二分法,我们分别从第一个和最后一个向中间进行扫描,并且计算出中间的数值与数组中的进行比较,可以通过计算中间值在这个数组中排多少位,然后得到比中间值小的或者大的数字有多少个,然后与 k 进行比较,如果比 k 小则说明中间值太小了,则向后移动,否则向前移动。
这个题目的二分确实很难想,我们来一步一步解释。
最普通的二分法是有序数组中查找指定值(或者说满足某个条件的值)这种思路比较直接,但是对于这道题目是二维矩阵,而不是一维数组,因此这种二分思想就行不通了。
378.kth-smallest-element-in-a-sorted-matrix-1
(普通的一维二分法)
而实际上:
  • 我们能够找到矩阵中最大的元素(右下角)和最小的元素(左上角)。接下来我们可以求出值的中间,而不是上面那种普通二分法的索引的中间。
378.kth-smallest-element-in-a-sorted-matrix-3
  • 找到中间值之后,我们可以拿这个值去计算有多少元素是小于等于它的。具体方式就是比较行的最后一列,如果中间值比最后一列大,说明中间元素肯定大于这一行的所有元素。 否则我们从后往前遍历直到不大于。
378.kth-smallest-element-in-a-sorted-matrix-2
  • 上一步我们会计算一个 count,我们拿这个 count 和 k 进行比较
  • 如果 count 小于 k,说明我们选择的中间值太小了,肯定不符合条件,我们需要调整左区间为 mid + 1
  • 如果 count 大于 k,说明我们选择的中间值正好或者太大了。我们调整右区间 mid
由于 count 大于 k 也可能我们选择的值是正好的, 因此这里不能调整为 mid - 1, 否则可能会得不到结果
  • 最后直接返回 start, end, 或者 mid 都可以,因此三者最终会收敛到矩阵中的一个元素,这个元素也正是我们要找的元素。
关于如何计算 count,我们可以从左下或者右上角开始,每次移动一个单位,直到找到一个值大于等于中间值,然后计算出 count,具体见下方代码。
整个计算过程是这样的:
378.kth-smallest-element-in-a-sorted-matrix-4
这里有一个大家普遍都比较疑惑的点,就是“能够确保最终我们找到的元素一定在矩阵中么?”
答案是可以, 因为我们可以使用最左二分,这样假设我们找到的元素不在矩阵,那么我们一定可以找到比它小的在矩阵中的值,这和我们的假设(最左二分)矛盾
不懂最左二分请看我的二分专题。

关键点解析

  • 二分查找
  • 有序矩阵的套路(文章末尾还有一道有序矩阵的题目)
  • 堆(优先级队列)

代码

代码支持:JS,Python3,CPP
JS:
1
/*
2
* @lc app=leetcode id=378 lang=javascript
3
*
4
* [378] Kth Smallest Element in a Sorted Matrix
5
*/
6
function notGreaterCount(matrix, target) {
7
// 等价于在matrix 中搜索mid,搜索的过程中利用有序的性质记录比mid小的元素个数
8
9
// 我们选择左下角,作为开始元素
10
let curRow = 0;
11
// 多少列
12
const COL_COUNT = matrix[0].length;
13
// 最后一列的索引
14
const LAST_COL = COL_COUNT - 1;
15
let res = 0;
16
17
while (curRow < matrix.length) {
18
// 比较最后一列的数据和target的大小
19
if (matrix[curRow][LAST_COL] < target) {
20
res += COL_COUNT;
21
} else {
22
let i = COL_COUNT - 1;
23
while (i < COL_COUNT && matrix[curRow][i] > target) {
24
i--;
25
}
26
// 注意这里要加1
27
res += i + 1;
28
}
29
curRow++;
30
}
31
32
return res;
33
}
34
/**
35
* @param {number[][]} matrix
36
* @param {number} k
37
* @return {number}
38
*/
39
var kthSmallest = function (matrix, k) {
40
if (matrix.length < 1) return null;
41
let start = matrix[0][0];
42
let end = matrix[matrix.length - 1][matrix[0].length - 1];
43
while (start < end) {
44
const mid = start + ((end - start) >> 1);
45
const count = notGreaterCount(matrix, mid);
46
if (count < k) start = mid + 1;
47
else end = mid;
48
}
49
// 返回start,mid, end 都一样
50
return start;
51
};
Copied!
Python3:
1
class Solution:
2
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
3
n = len(matrix)
4
5
def check(mid):
6
row, col = n - 1, 0
7
num = 0
8
while row >= 0 and col < n:
9
# 增加 col
10
if matrix[row][col] <= mid:
11
num += row + 1
12
col += 1
13
# 减少 row
14
else:
15
row -= 1
16
return num >= k
17
18
left, right = matrix[0][0], matrix[-1][-1]
19
while left <= right:
20
mid = (left + right) // 2
21
if check(mid):
22
right = mid - 1
23
else:
24
left = mid + 1
25
26
return left
Copied!
CPP Code:
1
class Solution {
2
public:
3
bool check(vector<vector<int>>& matrix, int mid, int k, int n) {
4
int row = n - 1;
5
int col = 0;
6
int num = 0;
7
while (row >= 0 && col < n) {
8
if (matrix[row][col] <= mid) {
9
num += i + 1;
10
col++;
11
} else {
12
row--;
13
}
14
}
15
return num >= k;
16
}
17
18
int kthSmallest(vector<vector<int>>& matrix, int k) {
19
int n = matrix.size();
20
int left = matrix[0][0];
21
int right = matrix[n - 1][n - 1];
22
while (left <= right) {
23
int mid = left + ((right - left) >> 1);
24
if (check(matrix, mid, k, n)) {
25
right = mid - 1;
26
} else {
27
left = mid + 1;
28
}
29
}
30
return left;
31
}
32
};
33
Copied!
复杂度分析
  • 时间复杂度:二分查找进行次数为 $O(log(r-l))$,每次操作时间复杂度为 O(n),因此总的时间复杂度为 $O(nlog(r-l))$。
  • 空间复杂度:$O(1)$。

相关题目

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 47K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。