LeetCode-74.-搜索二维矩阵
目录
LeetCode 74. 搜索二维矩阵
74. 搜索二维矩阵
给你一个满足下述两条属性的 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
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
题解
解法一
根据题目我们可以发现矩阵是从左到右一直非严格递增的
那么我们不妨将其化为一个非严格递增的一维数组
然后直接二分查找即可
代码如下↓
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
bool res=false;
int n=matrix.size();
int m=matrix[0].size();
vector<int> arr;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
arr.push_back(matrix[i][j]);
}
}
int l=0;
int r=m*n-1;
int k;
while(l<=r)
{
k=(l+r)/2;
if(arr[k]==target)
{
res=true;
break;
}
else if(arr[k]>target)
{
r=k-1;
}
else
{
l=k+1;
}
}
return res;
}
};解法二
解法与 相同
对于表格中任意一个数据，我们发现，其左边所有的数字都比其小，其下边所有数字都比其大
所以我们只需要比较其与 target 的大小关系，就可以排除其左边或右边
此外，如果我们比较的数据在最上或最右边，我们就可以排除一行或一列
因此，我们从右上角开始与target比较，一步步排除掉一行或一列，然后重复此步骤即可寻找完所有的数据
代码如下↓
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n=matrix.size();
int m=matrix[0].size();
int x=0;
int y=m-1;
bool res=false;
while(x>-1 && x<n && y>-1 && y<m)
{
if(matrix[x][y]==target)
{
res=true;
break;
}
else if(matrix[x][y]>target)
{
y--;
}
else
{
x++;
}
}
return res;
}
};