Keshawn_lu's Blog

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

字数统计: 708阅读时长: 3 min
2020/07/02 Share

题目简介:

给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。

示例:

1
2
3
4
5
6
7
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。

提示:
你可以假设 k 的值永远是有效的,1 ≤ k ≤ n2

思路:

利用二分查找,下界left为矩阵中数值最小的元素为左上角元素matrix[0][0],上界right为最大的元素,即右下角元素matrix[matrix.size() - 1][matrix.size() - 1]

将每次计算出来的mid与矩阵中的元素去比较,计算不大于mid的元素的数量。

由上图,取mid = 8 ,我们可以看到,矩阵中大于 mid 的数就和不大于 mid 的数分别形成了两个板块,沿着一条锯齿线将这个矩形分开。其中左上角板块的大小即为矩阵中不大于 mid 的数的数量。

我们只要沿着这条锯齿线走一遍即可计算出这两个板块的大小,也自然就统计出了这个矩阵中不大于 mid 的数的个数了。

走法演示如下,依然取 mid=8

走法文字描述如下:

  • 初始位置为matrix[n - 1][0](左下角)。
  • 设当前位置为matrix[i][j],若matrix[i][j] <= mid,那么第matrix[0 ... i][j]的值均小于mid,所以num += i + 1,并向右移动;否则向上移动(此时matrix[i][j] < mid)。
  • 不断移动直至走出边界。

统计矩阵中不大于mid的元素数量,若少于K,则说明答案x > midmid需要变大,即将left = mid + 1

不少于K,则说明答案x <= mid,将mid减少,即right = mid。(right = mid - 1会出错)

这样子,当while(left < right)条件不满足跳出循环时,所指的元素答案是唯一的,此时right == left,即区间里的元素只有一个。

最后返回left(或right)即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:

int check(vector<vector<int>>& matrix, int k, int mid){

int i = matrix.size() - 1;
int j = 0;
int num = 0;

while(i >= 0 && j < matrix.size()){

if(matrix[i][j] <= mid){

num += i + 1; //统计比mid小的元素数量
j++; //向右移动
}else{

i--; //元素比mid大, 向上移动
}
}

if(num < k)
return 0;
else
return 1;
}

int kthSmallest(vector<vector<int>>& matrix, int k) {

int n = matrix.size();
int left = matrix[0][0]; //最小值
int right = matrix[n - 1][n - 1]; //最大值

while(left < right){ //left != right(同样效果)

int mid = left + (right - left) / 2;

if(check(matrix, k, mid) == 0) //小于mid的值少于k, mid要变大
left = mid + 1;
else
right = mid; //小于mid的值大于等于k, mid要变小
}

return left; //right也对

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: