剑指offer面试题[3]-二维数组的查找

「爱情、让人受尽委屈。」 2022-06-15 10:15 163阅读 0赞

## 题目描述 ##

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

注：对于一个容器存储的二维数组，vector<vector<int>> array。

行数：row=array.size( );

列数：col=array\[0\].size( );

分析：

二维数组的特性如下所示，目标值target需要与数组的值进行比较，但是怎么比较呢？一个个遍历查找？显然一个个查找违背了题目的初衷，并且时间复杂度会过高，那从二维数组第一个元素array\[0\]\[0\]开始与target开始比较，如果 target<array\[0\]\[0\],很明显数组中是不存在target，因为array\[0\]\[0\]是最小元素，如果target>array\[0\]\[0\],那会出现一个问题，是列增加还是行增加呢？因为两个方向都是数值增加的方向。

所以得换一个位置，比如从最左下角元素array\[row-1\]\[0\]开始（当然最右上角元素也可以），如果target<array\[0\]\[0\],向上移动一行，反之向右移动一行，如果找到了target==array\[0\]\[0\]，则返回true。

![Center][]

接口函数：  
class Solution \{  
public:  
    bool Find(int target, vector<vector<int> > array) \{  
       int row=array.size();    //行数  
       int col=array\[0\].size(); //列数  
       for(int i=row-1;i>=0;i--)  
          \{  
            for(int j=0;j<col;j++)  
             \{  
                if(target==array\[i\]\[j\])  
                    return true;  
             \}          
          \}  
    return  false;  
    \}  
\};

[Center]: /images/20220615/e5408eada39a4931be6b26b5206ebb18.png