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

无标签

发布日期: 2023-06-26

更新日期: 2023-08-27

文章字数: 817

阅读时长: 3 分

阅读次数:

一、题目描述

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

示例

示例：
有二维数组矩阵如下：

[
  [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 = 20，返回 false。

限制

0 <= n <= 1000
0 <= m <= 1000

难度：中等

此题为中等，根据规律寻找的方法，着实是不能一下子想到！

二、思路分析

众所周知，力扣上，简单题是真简单，中等题有些困难，困难题看不懂答案。

题目解析

二维数组中的查找，根据题目描述，给到一个每行从左到右、每列从上到下满足递增顺序的二维数组，并在数组中寻找给定的目标值，存在返回 true，不存在返回 false。
对比一维数组中查找目标值，相同的，对于二位数组，无论是否有序，都可以通过一次完整的遍历并比较来判断是否存在，对于数组维数增加，算法的复杂度回平方增加，如果数量较大可能会超出时间限制。
由于题目给出的二维数组符合一定的排序规律，因此可以利用规律来减少比较次数
- 根据规律，数组最右侧元素作为一行中元素最大值，数组最上侧元素作为一列中最小值
- 可以以右上角元素作为切入，判断与目标值的关系
- 如果相等则返回 true；
- 如果小于目标值，则当前行中所有元素均小于目标值，此时行数 +1，继续比较下方元素
- 如果大于目标值，则当前列中所有元素均大于目标值，此时列数 -1，继续比较左侧元素
- 最终最多遍历比较一行和一列即 m+n 次既可得到最终结果。

三、AC 代码

遍历二维数组寻找目标值

遍历二维数组，逐个判断是否存在目标值，存在返回true，不存在则返回false，需要判断n的平方次

public boolean findNumberIn2DArray(int[][] matrix, int target) &#123;
  for(int i = 0; i < matrix.length; i++)&#123;
      for(int j = 0; j < matrix[0].length; j++)&#123;
          if(matrix[i][j] == target) return true;
      &#125;
  &#125;
  return false;
&#125;

通过边界判断

根据数组有序的规律，选择右上角元素，与目标值比较，如果小于，则增加行数，如果大于则减少列数，最多只需要判断 m+n 次

public boolean findNumberIn2DArray(int[][] matrix, int target) &#123;
  if(matrix.length == 0) return false;
  int row = 0, col = matrix[0].length-1;
  while(row < matrix.length && col >= 0)&#123;
      int cur = matrix[row][col];
      if(cur == target) return true;
      if(cur < target) row++;
      else col--;
  &#125;
  return false;
&#125;