一、问题
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例1
现有矩阵 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。
二、解法
解法一
思路：暴力法
这种方法未使用到条件左右有序和上下有序，但是这种方式比较通用。正常二维数组都可以查找
将数组完全遍历，找到target
时间复杂度O(n*m) 空间复杂度O(1)
具体实现：java
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(null == matrix||matrix.length==0){
return false;
}
for(int i = 0;i<matrix[0].length;i++){
for(int j = 0;j<matrix.length;j++){
if(matrix[j][i] == target){
return true;
}
}
}
return false;
}
解法二
思路：结合二分查找
- 首先，按行遍历每一行范围可以知道
- 如果target大于这一行的最小值和最大值
- 在行内进行二分查找
- 时间复杂度O(nlogm) 空间复杂度O(1)
具体实现：java
public boolean findNumberIn2DArray2(int[][] matrix, int target) {
if(null == matrix||matrix.length==0){
return false;
}
for (int i = 0; i < matrix.length; i++) {
if(matrix[i].length == 0){
return false;
}
if (matrix[i][0] <= target && matrix[i][matrix[i].length - 1] >= target) {
if (query(matrix[i], target)) {
return true;
}
continue;
}
}
return false;
}
/**
* 二分查找
* @param nums
* @param target
* @return
*/
public boolean query (int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return false;
}
解法三
思路：二叉搜索数
分析
因为数组是上下有序和左右有序的，那么可以知道，左上角的数是最小的，右下角的数是最大的。但是右上角和左下角这两个数比较特殊
右上角：右上角这个数，下面的数比他大，左边的数比他小。可知，很像二叉搜索树。左下角同理。
- 首先从右上角的数开始遍历。
- 如果target比这个数大，说明target如果存在，肯定在右上角这个数的下面。（因为左边的数都比target小，可以直接去除一行）
- 如果target比这个数小，说明target如果存在，肯定在右上角这个数的左面。（因为下面的数都比target大，可以直接去除一列）
- 时间复杂度O(n+m) 空间复杂度O(1)
具体实现：java
public boolean findNumberIn2DArray3(int[][] matrix, int target) {
if(null == matrix||matrix.length==0){
return false;
}
if (matrix[0] == null || matrix[0].length == 0){
return false;
}
for (int i = 0,j = matrix[0].length - 1; i < matrix.length && j >= 0;) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
j--;
} else {
i++;
}
}
return false;
}
