【leetcode】9. 数组-二维数组中的查找

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目

在一个 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)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;

    }
};