有序矩阵中第k小的元素（中等）

2020年7月2日

题目来源：力扣

力扣

排序

试验的做法，二维转一维再排序，花时间费空间

class Solution { public int kthSmallest(int[][] matrix, int k) { int mlen=matrix.length; int[] n_matrix=new int[mlen*mlen]; int count=0; for(int i=0;i<mlen;i++){ for(int j=0;j<mlen;j++){ n_matrix[count++]=matrix[i][j]; } } Arrays.sort(n_matrix); return n_matrix[k-1]; } }

二分

学习官方的二分题解，原来二分还能这么用，学到了学到了

class Solution { public int kthSmallest(int[][] matrix, int k) { //二维数组的长度，因为是n*n，所以算一个就行 int n = matrix.length; //左边界 int left = matrix[0][0]; //右边界 int right = matrix[n - 1][n - 1]; //使用二分，这里的>>1就是二进制的除以2 while (left < right) { int mid = left + ((right - left) >> 1); if (check(matrix, mid, k, n)) { right = mid; } else { left = mid + 1; } } return left; } //从左下角开始，符合小于等于mid就右移，不符合就上移，记录这一列小于mid的数量 public boolean check(int[][] matrix, int mid, int k, int n) { int i = n - 1; int j = 0; int num = 0; while (i >= 0 && j < n) { if (matrix[i][j] <= mid) { num += i + 1; j++; } else { i--; } } return num >= k; } }