原文 https://www.b2bchain.cn/5718.html
240. 搜索二维矩阵 II
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix==null||matrix.length==0||matrix[0].length==0) return false; int rows=matrix.length-1; int cols=matrix[0].length-1; int row=0; int col=cols; while(row<=rows && col>=0){ if(matrix[row][col]==target) return true; else if(matrix[row][col]<target) row++; else col--; } return false; } }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 。 // Related Topics 堆 二分查找 //leetcode submit region begin(Prohibit modification and deletion) class Solution { public int kthSmallest(int[][] matrix, int k) { int n=matrix.length-1; int left=matrix[0][0]; int right=matrix[n][n]; while(left<right){ int mid=left+(right-left)/2; if(checkNum(n,k,mid,matrix)) right=mid; else left=mid+1; } return left; } public boolean checkNum(int n,int k,int target,int[][] matrix){ int row=0; int col=n; int num=0; while(row<=n && col>=0){ if(matrix[row][col]<=target) { //这个位置是col+1 num+=col+1; row++; } else col--; } return num>=k; } } //leetcode submit region end(Prohibit modification and deletion)
