09
2020
03

剑指offer题目训练3:二维数组中的查找

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。

请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

样例

输入数组:

[
  [1,2,8,9],
  [2,4,9,12],
  [4,7,10,13],
  [6,8,11,15]
]

如果输入查找数值为7,则返回true,

如果输入查找数值为5,则返回false。


  1. 思路,乍一看没什么好的思路就是遍历一遍O(n2)。仔细观察这个二维数组行和列是有序的,我们可以从右上角的数字开始,如果查找值比这个数字大,那么这一行就不用找了,只需从下一行的右上角继续开始找;如果查找值比这个数字小,那么这个数字所在列及右边的列就不用找了,只需从前一列的右上角继续找,这样就会节省很多搜索的时间,复杂度为线性时间。这道题用了类似二分的思路,一种变形。

  2. 代码:


  3. class Solution {
    public:
        bool searchArray(vector<vector<int>> array, int target) {
            //数组为空,返回false
            if(array.empty()||array[0].empty()) return false;
            //数组右上角位置开始
            int i=0,j=array[0].size()-1;
            //不越界没找到就继续搜索
            while(i<=array[0].size()-1&&j>=0){
                //找到了,返回true
                if(array[i][j]==target) return true;
                //右上角值比要找的数小,直接找下一行
                if(array[i][j]<target) i++;
                //右上角值比要找的数大,直接找上一列
                else j--;
            }
            return false;
        }
    };
« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。