一、题目描述
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
二、输入描述
array: 待查找的二维数组
target:查找的数字
三、输出描述
查找到返回true,查找不到返回false
四、牛客网提供的类框架
class Solution {
public:
bool Find(vector<vector<int> > array,int target) {
}
};
五、解题思路
这道题类似于一维数组的二分查找。由题目可知矩阵是有序的,从左下角看,向上是递减,向右是递增(也可以从右上角看,向左是递减,向下是递增)。
所以从左下角开始或者从右上角开始查找。对于从左下角开始,当查找位置的数比要查找的数大,如果矩阵中该数存在,那么它将在该位置的上方,所以y坐标–;相反如果现在的位置上的书比要查找的数小,那么它将在该位置的右方,所以x坐标++。当所查找的位置超过矩阵的坐标范围,查找失败(数组中不存在该数)。同样也可以通过右上角开始查找。
六、代码
class Solution {
public:
bool Find(vector<vector<int> > array,int target) {
int row, column, i, j;
row = array.size();
column = array[0].size();
i = row - 1;
j = 0;
while(i >= 0 && j <= column -1)
{
if(array[i][j] < target)
{
j++;
}
else if(array[i][j] > target)
{
i--;
}
else{
return true;
}
}
return false;
}
};