剑指offer - 二维数组中的查找

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e

题意

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

题解

依次扫描的方法在此不表。
对于这样的四个数，a < b，c < d，a < c，b < d

所以a < c < d，a < b < d 。
由上述关系我们可以得到一种方法。从左下角出发，如果小于目标数则应该向右继续寻找，否则向上寻找，一直到等于目标数。如果越界则表示没有没有找到。
当然可以从右上角来寻找。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool Find(int  target, vector<vector<int> > array) {
        int i = array.size()-1,j=0;
        while(0<=i&&i<array.size()&&0<=j&&j<array[i].size()){
            if(target == array[i][j]) return true;
            else if(target > array[i][j]) j++;
            else if(target < array[i][j]) i--;
        }
        return false;
    }
};