题目

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

示例：

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

提示：
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n^2 。

解题思路

解法一：大根堆

略

解法二：二分查找

矩阵内的元素是从左上到右下递增的，整个二维数组中 matrix[0][0] 为最小值，matrix[n?1][n?1] 为最大值，现在将其分别记作 left 和 right。任取一个数 mid 满足 left ≤ mid ≤ right，那么矩阵中不大于 mid 的数，肯定全部分布在矩阵的左上角。
矩阵中大于 mid 的数就和不大于 mid 的数分别形成了两个板块，沿着一条锯齿线将这个矩形分开。其中左上角板块的大小即为矩阵中不大于 mid 的数的数量。只要沿着这条锯齿线走一遍即可计算出这两个板块的大小，也自然就统计出了这个矩阵中不大于 mid 的数的个数了。

可以这样描述走法：

• 1）初始位置在 matrix[n?1][0]（即左下角）；
• 2）设当前位置为 matrix[i][j]：
  • 2.1）若 matrix[i][j] ≤ mid，则将当前所在列的不大于 mid 的数的数量（即 i+1）累加到答案中，并向右移动；
  • 2.2）若 matrix[i][j] > mid，则暂不做统计，并向上移动。
• 3）不断移动直到走出格子为止。

不妨假设答案为 x，那么可以知道 left ≤ x ≤ right，这样就确定了二分答案的上下界。每次对于猜测的答案 mid，计算矩阵中目前有多少数小于等于 mid ：
1）如果数量大于等于 k，那么说明最终答案 x 小于等于 mid；
2）如果数量小于 k，那么说明最终答案 x 大于 mid。

假设矩阵中第k小的元素为a，第(k+1)小的元素为b，那么使得矩阵中有k个小于等于mid的元素，mid一定会在a与b之间，即 mid∈[a,b)（注：mid不一定是矩阵中的元素），而算法中最后返回的是left，也就是第一个满足有k个小于等于自身的元素，无疑a是第一个，所以找到的left一定是在矩阵中的。

复杂度分析：
时间复杂度：O(nlog(r?l))，二分查找进行次数为 O(log(r?l))，每次操作时间复杂度为 O(n)。
空间复杂度：O(1)。

代码

解法一：大根堆

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> b-a);
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                heap.add(matrix[i][j]);
                if(heap.size()>k){
                    heap.poll();
                }
            }
        }
        return heap.peek();
    }
}

解法二：二分查找

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;
    }

    private boolean check(int[][] matrix, int mid, int k, int n){
        int i = n-1;
        int j = 0;
        int cnt = 0;
        while(i>=0 && j<=n-1){
            if(matrix[i][j]<=mid){
                cnt += i+1;
                j++;
            }else{
                i--;
            }
        }
        return cnt>=k;
    }
}