蓝杉网站建设公司,个人微信网站建设,贵阳seo网站建设,推广员网站怎么做文章目录1 题目理解2 二分1 题目理解
输入#xff1a;一个mxn的int数组matrix#xff0c;这个数组每一行按照从小到大排序#xff0c;并且下一行的第一个值大于上一行的最后一个值。一个int值target 返回#xff1a;target在matrix中是否存在。存在返回true。
2 二分
我…
文章目录1 题目理解2 二分1 题目理解
输入一个mxn的int数组matrix这个数组每一行按照从小到大排序并且下一行的第一个值大于上一行的最后一个值。一个int值target 返回target在matrix中是否存在。存在返回true。
2 二分
我们可以把这个数组看做是一个有序数组。数组下表从0到m*n-1。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrixnull || matrix.length0 || matrix[0].length0) return false;int l 0;int r matrix.length*matrix[0].length-1;int cols matrix[0].length;while(lr){int m l ((r-l)1);int row m/cols;int col m%cols;if(matrix[row][col]target) return true;if(matrix[row][col]target){r m - 1;}else{l m 1;}}return false;}
}也可以先在第一列查找找到最小的比target大的元素所在的行l然后在l-1行查找target是否存在。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix null || matrix.length0 || matrix[0].length0) return false;int m matrix.length;int n matrix[0].length;//先在第一列找,l是nums[l]target的最小值int l 0, r m-1;while(lr){int middle l((r-l)1);if(matrix[middle][0] target) return true;if(matrix[middle][0]target){r middle-1;}else{l middle1;}}if(l0){int line l-1;//在line这一行查找l 0;r n-1;while(lr){int middle l ((r-l)1);if(matrix[line][middle]target) return true;if(matrix[line][middle]target){r middle-1;}else{l middle1;}}return false;}else{return false;}}
}
