LeetCode Hot100 搜索二维矩阵
给你一个满足下述两条属性的 m x n
整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target
,如果 target
在矩阵中,返回 true
;否则,返回 false
。
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出:true
示例 2:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出:false
思路
第一次
两次二分查找,先找行,再找列,注意数组不要越界。复杂度上logmn
第二次
当一维数组做,复杂度同logmn
代码
第一遍
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i = 0,j = matrix.size()-1;int m,row;while(i<=j){m = i+ (j-i)/2;if(matrix[m][0] == target)return true;else if(matrix[m][0] > target){j = m-1;}elsei = m+1;}if((row = i-1) < 0)return false;i = 0;j = matrix[0].size()-1;while(i<=j){m = i + (j-i)/2;if(matrix[row][m] == target)return true;else if(matrix[row][m] > target)j = m-1;elsei = m+1;}return false;}
};
第二遍
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i = 0,j = matrix.size()*matrix[0].size()-1;int m,size = matrix[0].size();int row,col;while(i<=j){m = i+ (j-i)/2;row = m/size;col = m%size;if(matrix[row][col] == target)return true;else if(matrix[row][col] > target){j = m-1;}elsei = m+1;}return false;}
};