剑指offer经典题目一:二维数组中的查找

x33g5p2x  于2022-01-11 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(271)

剑指offer经典题目一

题目链接二维数组中的查找
有一个二维数组,数组的每行从左到右是递增的,每列从上到下是递增的,在这样的数组中查找一个数字是否存在。要求时间复杂度小于O(N)。

解题思路

这道题本质上是查找一个数字,查找的过程,本质是排除的过程,如果一个一个遍历,一次只能排除一个,效率低,那么应该怎么做呢?这时我们需要用到这个数组的特性:数组的每行从左到右是递增的,每列从上到下是递增的,利用这个特性我们可以找到特殊的数字:右上角的数字或者左下角的数字,假如我们拿val值和右上角的数字进行比较,如果val值比该数字小,那么就排除了该右上角数字的那一列,剩下的数据中,我们可以继续找右上角的数字和val进行比较,继续进行排除,这样的方法效率就提升了很多,因为一次排除一行或者一列。什么时候查找结束呢?临界条件:如果从右上角的元素开始查找,那么边界条件就是i<array.size(),j>=0。

解题代码

class Solution
{
    public:
    bool Find(int val,vector<vector<int>> array)
    {
        int i = 0;
        int j = array[0].size()-1;
        //(i,j)是右上角的下标
        while(i < array.size() && j >= 0)//i小于行数,j>=0
        {
            if(val<array[i][j])
            {
                j--;//排除该列
            }
            else if(val>array[i][j])
            {
                i++;//排除该行
            }
            else
            {
                return true;
            }
        }
        return false;
    }
}

相关文章

微信公众号

最新文章

更多