在二维数组中查找元素

时间:2021-03-26 06:11:01

呐,乍一听,很简单啊。一个一个遍历过去不就好了嘛。啊哈哈,我还没有把题目贴完,如题:

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

有什么关系吗?我还是可以一个一个遍历啊。哎,好吧,不得不承认这也能解决问题。但是我今天要推出的解决方案有两种,如下:
方案一:找到可能存在该元素的所有行,然后对其进行二分查找。
方案二:将视点从左上角移动到左下角,就会发现:Val(i,j) > Val(i-1,j) Val(i,j) < Val(i,j+1), 所以我们可以从左下角的元素开始和目标元素进行匹配。如目标元素大于视点元素,则视点右移。若目标元素小于视点元素,则视点上移。若目标元素等于视点元素,就找到了。如果到了行列边界还没有找到,则没有找到元素。

方案二叙述了一大堆,肯定是比方案一更好的啊,实现也简单不少。如果我的文字描述能力不足以让你看懂,那么下面的代码一定能够让你看懂。

bool Find(vector<vector<int> > array,int target) 
{
int x = 0; //视点列号
int y = array.size()-1; //视点行号
while(y >= 0 && x<array[y].size())
{
if(array[y][x] > target) --y;
else if(array[y][x] < target) ++x;
else return true;
}
return false;
}

还好吧,都应该能看懂哦