题干:
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13
。
提示:
你可以假设 k 的值永远是有效的,1 ≤ k ≤ n2 。
读题后的第一思路:
说实话看完题干,我第一时间是没懂的,这个 k 到底代表着啥。
题中给了个 8, 总共 9个元素,也就是要返回第8小的元素,这里最小的是1,第8小的,也就是第2 大的,最大的是15,第二大的是13,所以返回了13,感觉挺绕的。
感觉对题目的理解还是不深,于是直接去评论区看看别人怎么读这道题:
本体使用的算法:归并排序。 普通归并排序是两个有序数组合并,这道题相当于 N 个有序数组合并,因此需要使用 N 个指针,归并到 第 K 个元素退出。
说实话,还是不太懂,直接抄一个解法吧 看看能不能从代码反推算法思想:
public int kthSmallest(int[][] matrix, int k) {
// 先定义行和列数
int n = matrix.length - 1;
// 分别是 第一个元素和最后一个元素
int l = matrix[0][0], r = matrix[n][n];
while (l < r) {
int mid = l + (r - l) / 2;
int count = countNoMoreThanMid(matrix, mid, n);
if (count < k) {
l = mid + 1;
} else {
r = mid;
}
}
return r;
}
private int countNoMoreThanMid(int[][] matrix, int mid, int n) {
int x = n, y = 0, count = 0;
while (x >= 0 && y <= n) {
if (matrix[x][y] <= mid) {
count += x + 1;
++y;
} else {
--x;
}
}
return count;
}
这效率可以啊,下面是对代码的理解:
写写画画了一堆,还是没懂,转而去看官方题解,原来这种方法是最后一种利用了矩阵所有特性的解法,使用了二分的思想。(只要是有序的,就可以使用二分)
首先给出矩阵的特性是:从左上到右下递增,那么可以画出下图:
- 二维数组的最小值是
matrix[0][0]
,最大值:matrix[n-1][n-1]
。这里将其分别记为l
和r
。 - 可以发现一个性质:任取一个数
mid
满足l <= mid <= r
,那么矩阵中不大于
mid 的数,肯定全部分布在矩阵左上角。
例如下图,取一个 mid = 8
:
可以看到,矩阵中大于 mid 的数 和不大于 mid 的数分别形成了2个板块,沿着一条锯齿线将这个句型分开,蓝色部分是不大于 mid
数的数量。
所以只要沿着这条锯齿线走一遍即可计算出这两个板块的大小,也就可以统计出这个矩阵中不大于 mid
的个数。
可以这样描述走法:
- 初始位置:
matrix[n-1][0]
(左下角) - 设当前位置为
matrix[i][j]
,若matrix[i][j] <= mid
则将当前所在列
的不大于mid
的数的数量(即i+1
) 累加到答案中,并向右移动
, 若matrix > mid
则向上移动
。 - 不断移动,直到走出矩阵格子。
这样走法的时间复杂度是
$$
O(n)
$$
即我们可以线性计算
对于任意一个 mid
,矩阵中有多少数不大于
它。这满足了二分查找
的性质。
假设答案为 x
,则可知
$$
l <= x <= r
$$
这样就确定了二分查找的上下界。
每次对于「猜测」 的答案 mid ,计算矩阵中有多少数不大于 mid:
- 如果数量
不少于 k
,则说明最终答案x
不大于mid
。 - 如果数量
少于 k
,那么说明最终答案x
大于mid
。
这样就可以计算出最终答案 x
。
Q.E.D.
Comments | 0 条评论