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

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

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

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

作者 | 程序员小吴

来源 | 五分钟学算法

题目描述

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

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

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

示例:

现有矩阵 matrix 如下:

[
  [1,   4,  71115],
  [2,   5,  81219],
  [3,   6,  91622],
  [1013141724],
  [1821232630]
]

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

本题知识点

查找、数组

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

有热门推荐👇

1.程序员全球最厉害的 14 位程序员

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

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!

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

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 图解「剑指Offer」之二维数组中的查找

我还会在以下平台发布内容

GitHub 哔哩哔哩