剑指 Offer 04. 二维数组中的查找
如图,18位于矩阵左下角,是所在列中最大的数字,在他所在行是最小的数,可以在左下角开始枚举。
设矩阵左下角值为x
- 若
target < x
,则排除当前所在的一整行 - 若
target > x
,则排除当前所在的一整列 - 若
target == x
,则返回true
枚举完整个矩阵则所求的值不在这个矩阵之中,返回false
同理,使用右上角的值也是可行的
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& array, int target) {
if(array.empty() || array[0].empty()) return false;
int n = array.size(), m = array[0].size();
int i = n - 1, j = 0;
while(i >= 0 && j < m) {
if(array[i][j] == target) return true;
if(array[i][j] > target) i -- ;
else j ++ ;
}
return false;
}
};