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

zhaojun

2022 年 10 月 07 日

17797 次浏览

2 条评论

465字数

默认分类

# [剑指 Offer 04. 二维数组中的查找](https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof)

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

示例:

现有矩阵 matrix 如下：

```java
[
  [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 = `5`，返回 `true`。

给定 target = `20`，返回 `false`。

**限制：**

`0 <= n <= 1000`

`0 <= m <= 1000`

## 题解 1 - 从左下角找

从左下角看，上方的数据都比下方的小，右侧的数据都比左侧的大。

设行数为 `rows`，列数为 `columns`，

从左下角找，所以 `x` 设为 `columns -  1`，`y` 设置为 0，如果元素等于 `target` 直接返会 `true`，如果元素大小 `target` 则 `x—`，如果元素小于 `taget` 则 `y++`，直到越数组边界未找到，返回 false.

```java
class Solution {

public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int rows = matrix.length;
        if (rows == 0) {
            return false;
        }

int columns = matrix[0].length;

int x = rows - 1, y = 0;

while (x >= 0 && y <= columns - 1) {
            int n = matrix[x][y];

if (n == target) {
                return true;
            } else if (n > target) {
                x--;
            } else {
                y++;
            }
        }

return false;
    }
}
```

## 题解 2 — 从右上角找

和题解 1 思路差不多，只是反过来而已

```java
class Solution {

public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int rows = matrix.length;
        if (rows == 0) {
            return false;
        }

int columns = matrix[0].length;

int x = 0, y = columns - 1;

while (x <= rows - 1 && y >= 0) {
            int n = matrix[x][y];

if (n == target) {
                return true;
            } else if (n > target) {
                y--;
            } else {
                x++;
            }
        }

return false;
    }
}
```

最后修改：2022 年 10 月 07 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

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

zhaojun • 2022 年 10 月 07 日

111
November 3rd, 2022 at 03:31 pm

123

回复
1. 123
  November 3rd, 2022 at 03:32 pm
  
  @111
  
  1231313
  
  回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

快帆云
你好，我们的机场：快帆云，已经稳定运营三年多，现在诚邀推广员。...
在nginx层面给任意项目站点增加访问限制：casdoor+oauth2-proxy - Blog By chenchen.site
[...]如果是宝塔用户可以直接使用以下方法安装模块，参考文章...
大概
你好，我就想整一个网盘，用作知识付费，就是普通用户只可以看到标...
zhao
测试
知名1842
表评论1842

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

2 条评论

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

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

宝塔 nginx 增加编译模块

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

ZFile 4.0.0 Bate 版本宝塔部署教程

leetcode 345 反转字符串中的元音字母

leetcode 3132. 找出与数组相加的整数 II

使用 Gost 来实现 sniproxy

Linux LVM 磁盘管理

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

2 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

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

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款