剑指 Offer——面试题 4-1

题目

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

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

样例

输入数组：

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

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

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

思路

首先这道题如果使用暴力做法，遍历数组的每个元素来进行查找的话，时间复杂度为O(n²)，这显然不是一个精妙的解法，我们要通过一些特殊的性质，来减少我们需要访问的元素个数

怎么做呢，我们可以看到，整个二维数组是每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，这是一条很重要的性质，也就是说，每一列的第一个元素是整列中最小的，每一行的第一个元素也是整行中最小的，我们可以从这个数组的右上角开始检测，如果右上角的元素大于target，我们就可以直接排除掉最右边的一列，因为target < 右上角元素 < 最右边的一列中其他元素，而如果右上角元素大于target，那么我们就可以删除最上边的一行，因为有target > 右上角元素 > 第一行中的其他元素，根据这个性质，我们可以每次去除二维数组的一行或者是一列，这样可以大大缩减我们查找所消耗的时间，下面看代码

代码

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if (array.size() == 0)
            return false;
        int i = 0;
        int j = array[0].size() - 1;
        while (i < array.size() && j >= 0) {
            if (array[i][j] == target)
                return true;
            if (array[i][j] > target) --j;
            if (array[i][j] < target) ++i;
        }
        return false;
    }
};

class Solution {
    public boolean searchArray(int[][] array, int target) {
        if (array.length == 0) return false;
        for (int i = 0, j = array[0].length - 1; i < array.length && j >= 0;) {
            if (array[i][j] == target) return true;
            if (array[i][j] > target) --j;
            else ++i;
        }
        return false;
    }
}