题目描述

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

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

样例

输入数组：

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

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

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

算法1

(暴力枚举) $O(n^2)$

两层循环枚举每一个数

时间复杂度

$O(n^2)$

C++ 代码

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if (array.empty()) return false;

        int n = array.size(), m = array[0].size();
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (array[i][j] == target)
                    return true;
        return false;
    }
};

算法2

(单调性扫描) $O(n + m)$

关键点是发现矩阵右上角这个点的性质，这个点左边的数都比它小，下边的数都比它大
根据这个性质，我们可以从右上角开始遍历矩阵，下标初始值 i = 0, j = m - 1

1. target == array[i][j] 返回 true
2. target < array[i][j]，目标值小于当前数，因为当前数下边的数都大于这个数，所以就可以少遍历一列，j --
3. target > array[i][j]，目标值大于当前数，因为当前数左边的数都小于这个数，所以就可以少遍历一行，i ++

时间复杂度

每次枚举一个数都可以少遍历一行或一列，最多遍历行号 + 列号（n + m）这么多次就可以找到答案，所以时间复杂度是线性的 $O(n + m)$

C++ 代码

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if (array.empty()) return false;

        int n = array.size(), m = array[0].size();
        int i = 0, j = m - 1;
        while (i < n && j >= 0)
        {
            if (target == array[i][j]) return true;
            else if (target < array[i][j]) j -- ;
            else if (target > array[i][j]) i ++ ;
        }
        return false;
    }
};