1.题目

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

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

示例 1：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：
输入：matrix = -5, k = 1
输出：-5

提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
题目数据保证 matrix 中的所有行和列都按非递减顺序排列
1 <= k <= n2

进阶：
你能否用一个恒定的内存(即 O(1) 内存复杂度)来解决这个问题?
你能在 O(n) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（this paper）很有趣。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix

2.思路

（1）排序（时空复杂度不符合题目要求）
比较容易想到的方法是先将矩阵转换为一维数组，然后再对一维数组进行排序，最后直接返回一维数组中的第 k 小元素即可。不过该方法的时间复杂度为 O(n2logn)，空间复杂度为 O(n2)，不符合题目要求。

（2）二分搜索
思路参考本题官方题解。

3.代码实现（Java）

//思路1————排序（时空复杂度不符合题目要求）
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] sortedNums = new int[rows * cols];
        int index = 0;
        //将二维数组转换为一维数组
        for (int[] row : matrix) {
            for (int num : row) {
                sortedNums[index++] = num;
            }
        }
        //对一维数组 sortedNums 进行排序
        Arrays.sort(sortedNums);
        //返回一维数组中的第 k 小元素
        return sortedNums[k - 1];
    }
}

//思路2————二分搜索
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) / 2);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    public boolean check(int[][] matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        // num 为矩阵中小于等于 mid 的元素的个数，初始值为 0
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }
}