《剑指Offer》二维数组中的查找

发表于 2023-04-12 更新于 2024-06-02 分类于剑指Offer 阅读次数：

题目：二维数组中的查找

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

[
 [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]
]

示例 1：

1 2	输入：plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8 输出：true

示例 2：

1 2	输入：plants = [[1,3,5],[2,5,7]], target = 4 输出：false

如果暴力法遍历所有数字，那么所用时间复杂度为O(mn)。

观察数组可以发现，数组中某一个数的右+下+右下部分均是大于该数的，一个数的左+上+左上部分均是小于该数的。拿数组中间的16举例，可以看到右下的加粗中数字都是大于16的，左上的斜体加粗中的数字都是小于16的。

[

[01, 04, 07, 11, 15],

[02, 05, 08, 12, 19],

[03, 06, 09, 16, 22],

[10, 13, 14, 17, 24],

[18, 21, 23, 26, 30]

]

我们可以改变遍历的方法，从左下角，如果比当前数字小，那么选择往上，如果比当前数字大，那么选择往右。

或者右上角开始，如果比当前数字小，那么选择往左，如果比当前数字大，那么选择往下。

解法一：从左下角开始遍历

从左下角开始遍历，如果比当前数字小，那么选择往上，如果比当前数字大，那么选择往右。

public boolean findNumberIn2DArray(int[][] matrix, int target) {
    if (matrix == null) {
        throw new IllegalArgumentException("数组为空");
    }
    int i = matrix.length - 1;
    int j = 0;
    while (i >= 0 && j < matrix[0].length) {
        if (target == matrix[i][j]) {
            return true;
        }
        else if (target > matrix[i][j]) {
            j++;
        }
        else {
            i--;
        }
    }
    return false;
}

时间复杂度O(m+n) 空间复杂度O(1)

题目：二维数组中的查找

解法一：从左下角开始遍历

相关代码