算法题-二维数组中的查找

发表于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

题目

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
现有矩阵 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，返回 true。
给定 target = 20，返回 false。

限制：
0 <= n <= 1000
0 <= m <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

  1. 由题可知：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
  2. 因此可以关注左上和右下两点，以左上顶点为例，若 target 小于 *matrix[i][j]*，则 target 所在区域必在其 左侧（即 i–），若 target 大于 *matrix[i][j]*，则 target 所在区域必在其 下方（即j++）;
  3. 若 索引越界 则表示在 matrix 中找不到对应的 target，返回 false

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        int i = 0;
        int j = matrix[0].length - 1;
        while (true) {
            if (i >= matrix.length || j < 0) {
                return false;
            }
            if (matrix[i][j] == target) {
                return true;
            }
            if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
    }
}

总结

  • 对于从左到右递增且从上到下递增的二维数组的遍历可以考虑从左上或者右下开始