视频讲解 | 图解剑指offer：二维数组的查找

不念不忘少年蓝@ 2023-06-29 02:25 103阅读 0赞

前几天在 B 站录制了一个视频，讲解剑指offer上的一道题目「二维数组的查找」，以下为该视频的文字版讲解，感兴趣的可以在文章后面扫描二维码观看视频。

### 题目描述 ###

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

编写一个高效的算法来搜索 *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` 小，则说明应该找更大的，往下走。

### 视频讲解 ###

![format_png][]

### 代码实现 ###

//@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)。没有使用额外的存储空间，所以它的内存占用是恒定的。

### 本题知识点 ###

查找、数组

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRFVlZoaWFVZGNOaWJad0o1OWZGdmpmM3hBbFBFOWVpY1QxanhDSU5oQUk4cnpmWmRhblVMVkhTRzVmajczR0Rhc0xpY2RNUWlhMElZY0I2US82NDA?x-oss-process=image/format,png