图解「剑指Offer」之二维数组中的查找

以你之姓@ 2024-04-18 15:29 113阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | 程序员小吴

来源 | 五分钟学算法

### 题目描述 ###

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

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

*  每行的元素从左到右升序排列。
 *  每列的元素从上到下升序排列。

**示例:**

现有矩阵 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`，目标值 **5** 在这个数组中，返回 `true` 即可。

给定 target = `20`，目标值 **20** 不在这个数组中，需要返回 `false` 。

### 题目分析 ###

这个二维数组是有特点的：

*  每一行都是**递增**的
 *  每一列都是**递增**的

首先，我们初始化一个指向矩阵右上角的 **元素** 。

从这个元素开始查找，如果这个元素比 `target` 大，则说明需要找更小的，往左走；如果这个元素比 `target` 小，则说明应该找更大的，往下走。

### 动画演示 ###

### 代码实现 ###

//@author:程序员小吴
    public class Solution {
      public boolean Find(int target, int [][] array) {
        //边界条件判断
        if (array == null || array.length == 0 ||
          array[0] == null || array[0].length == 0)
          return false;
        //获取函数矩阵的行数 m 与列数 n
        int m = array.length, n = array[0].length;
        //初始化一开始的元素位置，这里我们设置为矩阵最右上角的元素
        int i = 0, j = n - 1;
        //循环遍历整个函数
        while (i < m && j >= 0) {
          //如果目标值小于右上角的数字，则列下标减一
          if (target < array[i][j]) j--;
          //如果目标值大于右上角的数字，则行下标加一
          else if (target > array[i][j]) i++;
          //如果相等，直接 true
          else return true;
        }
        //循环结束后如果还没有找到目标时，返回 false
        return false;
      }
     }

### 复杂度分析 ###

*  时间复杂度：O(n+m) 。在循环语句中，除非直接返回结果，否则每一次行都会递减一次或者列都会递增一次。该矩阵共有 m 行 n 列，因此循环终止之前，循环不会运行超过 n+m 次。其它的操作都是常数，所以总的时间复杂度是线性的。
 *  空间复杂度：O(1)。没有使用额外的存储空间，所以它的内存占用是恒定的。

### 本题知识点 ###

查找、数组

![640?][640]

**有热门推荐?**

1.【程序员】[全球最厉害的 14 位程序员][14]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了][Link 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/13d08d7699a94d0fa7d37f478577ffa5.png
[640]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/af371967ee1b422fa83c4121ab342c65.gif
[14]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486099&idx=1&sn=6ea84944fe6a3d6dd1af2b00f3e53002&chksm=fa0e6512cd79ec04c8e8c63e74d78cc23629b88290a8e0642e5e44601f99fc39a3ea530867bc&scene=21#wechat_redirect
[GitHub]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486254&idx=1&sn=654c208601879fe1b76c682a069a4e6a&chksm=fa0e64afcd79edb960a9863c7af7e6de5893da2326e6eca2bcd9d68061966d200ba0e189ab91&scene=21#wechat_redirect
[KMP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485939&idx=1&sn=b25f39b5644da92c4047bbbd9936f73c&chksm=fa0e6672cd79ef64dda0a21e23c2817edf4a64cbb75b9bed328d6519c6cd4fef36d03a4cb309&scene=21#wechat_redirect
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[640_wx_fmt_jpeg 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b3bf4ab4a3f04e019568088db5db3720.png