牛客之二维数组中的查找
程序员文章站
2022-07-12 09:17:20
...
题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
方法1:循环遍历,一个一个比较
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int flag=0;
int m=0;
for (int i = 0; i < array.size();i++ )
{
for(int j=0;j<array[0].size();j++)
if(target==array[i][j])
{
flag=1;
goto judge;
}
}
judge:
if(flag==1)
return true;
else
return false;
}
};
方法2:target值分别与每行的行首和行位比较,在其中之间则遍历比较该行,没找到继续寻找符合条件的下一行
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if (array.empty())
return false;
int flag=0;
int i=0;
int j=0;
int len=array[0].size();
while(i<array.size()&&j<len)
{
if(target==array[i][j])//每行第一个元素
{
flag=1;
break;
}
if(target<=array[i][len-1]&&target>array[i][j])//在每行的头尾之间
for(int m=j;m<len;)//遍历该行
if(target==array[i][m])//zhao dao
{
flag=1;
goto judge;
}
else
m++;
if(flag==0)//检测符合条件的该行后,继续检测下面是否有符合条件的行
{
j=0;
i++;
}
}
judge:
if(flag==1)
return true;
else
return false;
}
};
上一篇: AcWing 15 二维数组中的查找
下一篇: 面试常用查找算法