剑指offer-3.二维数组中查找
0 题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列按照从上到下递增顺序排序
请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有这个整数。
1 分析
凡是数组有序的首先要想到的是二分查找。
这个二维数组的特点在于，数组中某个点，在该点，右、下方的数都比该数大。左、上的都比该数小。
但是同时判断两个相同维度，比较麻烦。
因此先判断两个不同的维度。也就是说，判断某个点右面和下面，或是左面和上面。那么其中一个方向是大的，另一个方向是小的。
以判断右面和下面为例：
去左上的点开始，首先，如果目标数比当前点大，那么向下移动，如果比目标点小，那么向右面移动，此时点的右下就是带选择的区域，坐下就是筛选过的区域
bool find(int target, vector<vector<int>> array)
{
size_t rows = array.size();
if (rows == 0)
{
return false;
}
size_t cols = array[0].size();
if (cols == 0)
{
return false;
}
// col,和row 是右上的点
int col = cols - 1;
int row = 0;
// 点向左下移动，因此，col>=0, row < rows
while (col >= 0 && row < rows)
{
if (target == array[row][col])
{
return true;
}
else if (target < array[row][col]) // 大于，向下移动
{
--col;
}
else if (target > array[row][col]) // 小于，向左移动
{
++row;
}
}
return false;
}
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。