74. 搜索二维矩阵
难度中等249
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false通过次数63,695
提交次数163,381
题解
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) {
return false;
}
if (matrix[0].length == 0) {
return false;
}
if (matrix[0][0] == target) {
return true;
}
int row = matrix.length;;
int col = matrix[0].length;
if( target < matrix[0][0] || target > matrix[row-1][col-1]) return false;
//查找行
List<Integer> row_temp = new ArrayList<>();
for(int i =0; i < row; i++){
row_temp.add(matrix[i][0]);
}
int l = 0;
int r = row_temp.size();
while( l < r){
int mid = l + ( r - l)/2;
if(row_temp.get(mid) == target) return true;
else if( row_temp.get(mid) > target){
r--;
}else{
l++;
}
}
//查找列
List<Integer> col_temp = new ArrayList<>();
for(int i = 0; i < col; i++){
col_temp.add(matrix[l-1][i]);
}
int col_l = 0;
int col_r = col_temp.size();
while( col_l < col_r){
int col_mid = col_l + (col_r - col_l)/2;
if( target == col_temp.get(col_mid)){
return true;
}
else if(col_temp.get(col_mid) < target ){
col_l = col_mid+1;
}else{
col_r = col_mid;
}
}
return false;
}
}转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com