二维数组中的查找
题目描述
在一个 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。
1：枚举
遍历整个二维数组，当遇到等于target的值时，返回
class Solution {
public boolean findNumberIn2DArray(int[][] matrix
, int target
) {
int row
= matrix
.length
;
if(row
==0) return false;
int col
= matrix
[0].length
;
for(int i
= 0; i
< row
; i
++) {
for(int j
= 0; j
< col
; j
++) {
if(matrix
[i
][j
]==target
) return true;
}
}
return false;
}
}
时间复杂度：O(n^2)，空间复杂度：O(1)
2：线性查找
对于二维数组的行：从左到右递增；列：从上到下递增即：可以拿target与每行最后一位数(num)作比较
num>target：列数递减，直到与target相等num=target：直接返回num<target：行数递增，直到num>target后列数递减或num=target直接返回
class Solution {
public boolean findNumberIn2DArray(int[][] matrix
, int target
) {
if(matrix
== null
|| matrix
.length
==0 || matrix
[0].length
== 0) return false;
int rows
= matrix
.length
, cols
= matrix
[0].length
;
int row
= 0, col
= cols
- 1;
while(row
<rows
&&col
>=0) {
int tmp
= matrix
[row
][col
];
if(tmp
>target
) {
col
--;
} else if(tmp
<target
) {
row
++;
} else {
return true;
}
}
return false;
}
}
时间复杂度：O(n)，空间复杂度：O(1)
