侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

04 二维数组中的查找

Lin2J
2021-07-19 / 0 评论 / 0 点赞 / 114 阅读 / 1,045 字 / 正在检测是否收录...

剑指 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)$:使用常数级的空间。

0

评论区