【每日一题】【leetcode】9. 数组-二维数组中的查找

题目

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 难易程度：easy

示例:

现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]

给定 target = 5，返回 true。 给定 target = 20，返回 false。

限制：

0 <= n <= 1000 0 <= m <= 1000

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

分析

本题抓住两个点：

1. 每一行都按照从左到右递增的顺序排序
2. 每一列都按照从上到下递增的顺序排序

以上两点说明：

1. 矩阵matrix中小于matrix[i][j]的元素只能出现在该元素所在列的左侧或者上侧，即列坐标小于j或者行坐标小于i
2. 矩阵matrix中大于matrix[i][j]的元素只能出现在该元素所在列的右侧或者下侧，即列坐标大于j或者行坐标大于i

我们从右上角开始遍历：

1. matrix[i][j] == target,返回 true
2. matrix[i][j] > target, 由说明1可知target只可能出现在左侧（matrix[i][j]右&上侧的数据已经遍历过了），则i++
3. matrix[i][j] < target, 由说明2可知target只可能出现在下侧（matrix[i][j]右&上侧的数据已经遍历过了），则j--

时间复杂度：O(N) 空间复杂度：O(1)

代码

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        if (n == 0) {
            return false;
        }
        int m = matrix[0].size();
        int i = 0, j = m - 1;

        while (i < n & j >= 0) {
            if (target == matrix[i][j]) {
                return true;
            } else if (matrix[i][j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return false;

    }
};