题干:

给定一个 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;
    }

image-20200901233909025

这效率可以啊,下面是对代码的理解:

写写画画了一堆,还是没懂,转而去看官方题解,原来这种方法是最后一种利用了矩阵所有特性的解法,使用了二分的思想。(只要是有序的,就可以使用二分)

首先给出矩阵的特性是:从左上到右下递增,那么可以画出下图:

image-20200902011910116

  • 二维数组的最小值matrix[0][0] ,最大值:matrix[n-1][n-1]。这里将其分别记为 lr
  • 可以发现一个性质:任取一个数 mid 满足 l <= mid <= r ,那么矩阵中不大于 mid 的数,肯定全部分布在矩阵左上角

例如下图,取一个 mid = 8

image-20200902012932681

可以看到,矩阵中大于 mid 的数 和不大于 mid 的数分别形成了2个板块,沿着一条锯齿线将这个句型分开,蓝色部分是不大于 mid 数的数量。

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

image-20200902014841412

可以这样描述走法:

  • 初始位置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.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。