leetcode-数组-medium-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 。

读题后的第一思路：

说实话看完题干，我第一时间是没懂的，这个 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 则向上移动。
不断移动，直到走出矩阵格子。