剑指offer1_二维数组中的查找

题目描述

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

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M

题目链接：剑指offer1 二维数组中的查找

C++解题

思路1：遍历二维vector

代码如下：

class Solution 
{
public:
    bool Find(int target, vector<vector<int> > array) 
    {
        int i=0,j=0;
        for(i=0;i<array.size();++i) //注意这里对于二维vector的操作
        {
            for(j=0;j<array[0].size();++j)
            {
                if(target==array[i][j])
                    return true;
            }
        }
        return false;
    }
};

复杂度分析：行列均遍历一遍，复杂度为\(O(n^2)\)

思路2：遍历列，对行进行二分查找

代码如下：

class Solution 
{
public:
    bool Find(int target, vector<vector<int> > array) 
    {
        int i=array.size();
        for(i=0;i<array.size();++i)
        {
            int low=0;
            int high=array[i].size()-1;
            int mid=0;
            while(low<=high)  //注意二分查找终止条件 <=
            {
                mid=(low+high)/2; //注意这里需要更新mid，不用严格考虑奇偶
                //注：为防止low+high溢出，则上方表达式应该为mid=low+(high-low)/2
                if(target==array[i][mid])
                    return true;
                else if(target<array[i][mid])
                    high=mid-1;
                else
                    low=mid+1;
            }
        }
        return false;
    }
};

复杂度分析：列遍历一遍，行二分查找，复杂度为\(O(nlog(n))\)

思路3：根据数据信息，选择从左下角/右上角开始查找

思路描述：因为每行从左到右依次变大，每列从上到下依次变大。以从右上角出发为例，若target大于该值则向下查询，若target小于该值则向左查询。因为比该值大的只可能在下方或下左方，比该值小的只可能在左方或者左下方，而从右上方开始搜索，最坏的情况为target不在数组中，此时需要搜索的次数是2n次，即时间复杂度为\(O(n)\)

代码如下：

class Solution 
{
public:
    bool Find(int target, vector<vector<int> > array) 
    {
        // 从右上角开始向左向下搜索
        int row=0;
        int col=array[0].size()-1; // 注意这里是n-1
        while(col>=0&&row<array.size())
        {
            if(target==array[row][col])
                return true;
            else if(target>array[row][col]) // target大于当前位置，向下搜索
                row=row+1;
            else // target小于当前位置，向左搜索
                col=col-1;
        }
        return false;
    }
};

复杂度分析：特殊查找类型，相当于只把某1行和某1列进行了查找，复杂度为\(O(n)\)

知识点总结

1. C++ STL的vector操作
2. 二分查找mid的设置和更新，可以用while也可以用递归，记住边界条件
3. 思路2、3中的搜索方法，值得记住