更新时间:2022-04-26 03:35:30
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性:
在线评测地址:领扣题库官网
样例 1:
输入: [[5]],2
输出: false
样例解释:
没有包含,返回false。
样例 2:
输入:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
],3
输出: true
样例解释:
包含则返回true。
解题思路:
题目提到,给定的数组已经排序,若是一个一维数组,直接一次二分查找即可。现在题目给了一个二维数组,那么处理一下数组的下标,仍然按照一维数组二分即可。
二分查找常用于查找有序数组中目标数target的位置,用left和right记录target所在的区间端点,每次将区间的中间位置值和target作比较,然后移动区间端点。
算法流程:
public class Solution {
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int col = matrix[0].length;
int left = 0, right = n*col - 1;
while(left < right){
int mid = (right + left) / 2;
if(matrix[mid/col][mid%col] == target){
return true;
}
else if(matrix[mid/col][mid%col] > target){
right = mid;
}
else{
left = mid + 1;
}
}
if(matrix[right/col][right%col] == target){
return true;
}
return false;
}
}
更多题解参考:九章官网Solution