做地方旅游网站目的意义,如何在百度上做网站,找个人给我做电影网站好,建设工程信息网为官方网站给你一个满足下述两条属性的 m x n 整数矩阵#xff1a;
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target #xff0c;如果 target 在矩阵中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。…给你一个满足下述两条属性的 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(vectorvectorint matrix, int target) {int i 0,j matrix.size()-1;int m,row;while(ij){m i (j-i)/2;if(matrix[m][0] target)return true;else if(matrix[m][0] target){j m-1;}elsei m1;}if((row i-1) 0)return false;i 0;j matrix[0].size()-1;while(ij){m i (j-i)/2;if(matrix[row][m] target)return true;else if(matrix[row][m] target)j m-1;elsei m1;}return false;}
}; 第二遍
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int i 0,j matrix.size()*matrix[0].size()-1;int m,size matrix[0].size();int row,col;while(ij){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 m1;}return false;}
};
