AcWing 15. 二维数组中的查找
原题链接
中等
作者:
腾杨天下
,
2021-11-08 04:36:53
,
所有人可见
,
阅读 464
每一行二分Onlogn
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& a, int target) {
for(int x=0;x<a.size();x++)
{
int l=0,r=a[0].size();
while(l<r)
{
int mid=l+r>>1;
if(a[x][mid]<target)l=mid+1;
else r=mid;
}
if(l>=a[0].size())continue;
if(a[x][l]==target)return true;
}
return false;
}
};
右上角往左下On
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& a, int target) {
if(!a.size())return false;
int n=a.size(),m=a[0].size();
int x=0,y=a[0].size()-1;
while(x<n&&y>=0)
{
if(a[x][y]==target)return true;
if(a[x][y]>target)y--;
//如果a[x][y]>target代表从a[x][y]~a[n-1][y]都>target,所以直接把最后一列删去
else if(a[x][y]<target)x++;
//如果a[x][y]<target代表从a[x][y]~a[x][m-1]都<target,所以直接把第一行删去
}
return false;//没找着返回false
}
};
被头像吸引。。