04 二维数组中的查找

剑指 Offer 04. 二维数组中的查找

解题思路：

因为题目中说明了每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。因此对于数组中的某个数字 $a$ ，如果 $target$ 比 $a$ 小，说明 $target$ 在 $a$ 上方。如果 $target$ 比 $a$ 搭，说明 $target$ 在 $a$ 的右方。

为了方便描述，将一个二维数组的四条边分为上下左右四个方向。

算法流程：

1. 从二维数组 $matrix$ 的左下方开始遍历，索引设置为 $(i, j)$，并与目标值 $target$ 比较大小。
   1. 如果 $matrix[i][j]$ 等于 $target$，那么直接返回 $true$ 。
   2. 如果 $matrix[i][j]$ 大于 $target$，说明 $target$ 在 $matrix[i][j]$ 的上方，那么 $i--$。
   3. 如果 $matrix[i][j]$ 小于 $target$，说明 $target$ 在 $matrix[i][j]$ 的右方，那么 $j++$。
2. 如果遍历完之后，没有返回，则找不到 $target$，返回 $false$。

代码：

public boolean findNumberIn2DArray(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0) {
        return false;
    }
    int i = matrix.length - 1;
    int j = 0;
    while (i >= 0 && j < matrix[0].length) {
        if (matrix[i][j] == target) {
            return true;
        }
        if (matrix[i][j] > target) {
            i--;
        } else {
            j++;
        }
    }
    return false;
}

复杂度分析

• 时间复杂度$O(M+N)$：其中，$M$ 和 $N$ 是矩阵的行数和列数，此算法最多循环 $M + N$ 次。

• 空间复杂度$O(1)$：使用常数级的空间。