二维数组中的查找

二维数组中的查找

题目描述

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

示例

现有矩阵 matrix 如下:

1
2
3
4
5
6
7
[
[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
3
4
5
6
7
8
9
10
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
for (int[] inner : matrix) {
for (int i : inner) {
if (i == target) return true;
}
}
return false;
}
}

解法二

二维矩阵中每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序的特点,说明对于任意一个数字,它左边的数字都比他小,下面的数字都比他大

我们可以从右上角开始查找,设当前值为 value = matrix[i][j]:

  1. 如果 value < target,那么我们就需要更大的值,即使 i++,以切换到下一行
  2. 如果 value > target,那么我们就需要更小的值,即使 j–,以切换到左边一个数字
  3. 如果 value == target,那么即可返回 true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
int[] inner = matrix[i];
for (int j = inner.length - 1; j > -1; j--) {
int value = matrix[i][j];
if (value == target) {
return true;
} else if (value < target) {
break;
}
}
}
return false;
}
}