leetcode-kth-smallest-element-in-a-sorted-matrix

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

　　矩阵每行和每列都是从小到大排好序的，求第k小的元素

题目分析

　　本题可以使用堆，但是最优的方法是二分答案法，答案的区间就是在matrix[0][0]到matrix[n-1][n-1]之间，本题等价于求matrix中排序小于等于k的最大值，因此check方法就是求：如果v在matrix排序小于等于k就返回true，否则返回false。注意check方法中v和matrix[i][j]比较的处理，三种情况都要分别算，还有matrix中实际上会有重复的元素，check检测的是值为v的元素在matrix中排序以后的最小排名小于等于k就返回true

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
  
    private boolean check(int[][] matrix, int k, int v) { // v在matrix中排名小于等于k则返回true，否则返回false
        int n = matrix.length;
        int i = n - 1;
        int j = 0;
        int ans = 0;
        while (i >= 0 && j <= n - 1) {  // 从矩阵左下角开始，每次可以去掉一行/一列
            if (v > matrix[i][j]) {
                ans += (i + 1);
                j++;
            } else if (v == matrix[i][j]){ // 注意等于的情况
                ans += i;
                j++;
                i--;
            } else {
                i--;
            }
        }
        return (ans + 1 <= k);
    }
    
    public int kthSmallest(int[][] matrix, int k) {
        
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1] + 1;
        while (left + 1 < right) {  // [left,right)
            int mid = left + ((right - left) >> 1);
            if (check(matrix, k, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
        
    }
}

　　算法复杂度：O(n * log(矩阵最大值 - 矩阵最小值)) n为正方形的长度