欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客之二维数组中的查找

程序员文章站 2022-07-12 09:17:20
...

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

方法1:循环遍历,一个一个比较

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int flag=0;
        int m=0;
	for (int i = 0; i < array.size();i++ )
    {
        for(int j=0;j<array[0].size();j++)
            if(target==array[i][j])
            {
                flag=1;
                goto judge;
            }
    }
judge:
        if(flag==1)
            return true;
        else
            return false;
    }
};

方法2:target值分别与每行的行首和行位比较,在其中之间则遍历比较该行,没找到继续寻找符合条件的下一行

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
         if (array.empty())
             return false;
        int flag=0;
        int i=0;
        int j=0;
        int len=array[0].size();
        while(i<array.size()&&j<len)
        {
            if(target==array[i][j])//每行第一个元素
            {
                flag=1;
                break;
            }
            if(target<=array[i][len-1]&&target>array[i][j])//在每行的头尾之间
                for(int m=j;m<len;)//遍历该行
                    if(target==array[i][m])//zhao dao
                    {
                        flag=1;
                        goto judge;
                    }
                    else
                        m++;
            if(flag==0)//检测符合条件的该行后,继续检测下面是否有符合条件的行
            {
                j=0;
                i++;
            }
        }
        judge:
        if(flag==1)
            return true;
        else
            return false;
    }
};
相关标签: 查找