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

待我称王封你为后i 2022-02-21 14:36 260阅读 0赞

##### 题目描述 #####

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

##### 实现思想 #####

①首先要确定数组是有序的，并且有序的方式是从左上角到右下角数组的值依次增大。  
②从左下角开始目标值与数组值进行比较。（重要思想：左下角开始）  
③如果目标值小于当前指向的数组值，指向后移，如果目标值大于指向的数组值，指向上移，如果目标值等于指向数组值，返回True，如果最终指向行小于0或者是列大于数组的列了（也就是超出数组的界限依旧没有找到目标值），就返回Flase，代表数组中没有目标值。

##### 代码实现 #####

#include <stdc++.h>
    
    using namespace std;
    
    class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            int row = array.size();
            int col = array[0].size();
            int i = row-1;
            int j = 0;
            cout << "row:"<<row<<" col:"<<col<<endl;
            while(j < col && i >= 0)
            {
                if(target > array[i][j])//如果target大并且没超出范围就往后移动
                {
                    j++;//向后移动
                }
                else if(target < array[i][j])
                {
                    i--;//向上移动
                }
                else if(target == array[i][j])
                    return true;
    
            }
    
            return false;
        }
    };
    
    int main()
    {
        Solution S;
        vector<vector<int> > array;
    
        for(int i = 0; i < 10; i++)
        {
            vector<int> array_raw;
            for(int j = 0; j < 10 ; j++)
            {
                array_raw.push_back((i+2)*j);
            }
            array.push_back(array_raw);
        }
        //输出看看
        for(int i = 0; i < 10; i++)
        {
            for(int j = 0; j < 10 ; j++)
            {
                cout << array[i][j] << " ";
            }
            cout << endl;
        }
        if(S.Find(19, array))
            cout<<"数字在数组中";
        else
            cout<<"数字不在数组中";
        return 0;
    }

##### 运行截图 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]

##### 总结 #####

1.  `vector<vector<int> > array;`  
    是利用向量中存放向量的方式来生成一个二维向量（也可叫做二维数组），所以输入的方式需要先生成一个一维向量，然后将一维向量`push_back()`进二维向量，这样来生成一个数组，但是访问二维向量的时候，与访问数组的方式是一样的。
2.  不管是二维数组还是二维向量，都可以用`int row = array.size(); int col = array[0].size();` 这种方式来读取行和列。
3.  以后如果碰到从左上角到右下角依次递增的数组可以用这种方式查找数组中元素：从左下角开始，如果查找的数大，就往后移动，如果查找的数小就往上移动，如果找到就返回True，如果直到行或者列越界，就返回False。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]: /images/20220221/d845eb28f70c4ede8f58b5cfb3c6f296.png