Search a 2D Matrix 搜寻一个二维数组
题目:
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
题意很好理解,便是从一个二维数组中寻找一个值。如果存在这个值,便返回true,否则false。值得注意的是这个数组的行和列都是从小到大排序的,并且每一行的第一个值都比前一行的最后一个值大。这个性质之后可以用到。
Approach One: Brute Force 暴力解:
第一种解非常容易想到,便是对矩阵的每一列及每一行进行遍历,如果找到值,就返回true,否则返回false。
时间复杂度: O(n*m)。n和m为数组的行和列的长度。
空间复杂度: O(1)。 没有用到额外的空间。
可以看到时间复杂度非常大,可能会导致超时,所以我们想一个其他方法。
Approach Two: Variation of Linear Search 线性寻找(kind of)
第二种方法是从这个矩阵的一个角开始找起,以下的code是从矩阵的右上角开始,如果当前的值比要寻找的值小,则往前看一位(也就是往前看一列),反之则往下看一位(也就是往下看看一行)直到找到为止,找不到就返回false。这个方法用到了矩阵的行和列是排好序的性质。
时间复杂度: O(n+m)。n和m为数组的行和列的长度。最差的情况便是从一个角遍历到了对角(e.g. 从右上角遍历到了左下角)。
空间复杂度: O(1)。 没有用到额外的空间
// linear search: O(n+m)
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null||matrix.length==0) return false;
int row=0, col=matrix[row].length-1;
while(row<matrix.length && col>=0) {
if(matrix[row][col]==target) {
return true;
} else if(matrix[row][col]>target) {
col--;
} else{
row++;
}
}
return false;
}
Approach Three: 二分搜索法
由于行和列是排序的,所以很容易联想到二分搜索。即是先对对矩阵的行进行查找,当找到一个可能包含这个值的行时,再进行第二次二分搜索。注意的是必须先对行进行查找,也就是matrix[row][0],不然会有bug。
时间复杂度: O(logn+logm)。n和m为数组的行和列的长度。每次只需寻找当前数组范围的一半。
空间复杂度: O(1)。 没有用到额外的空间
// Binary Search: O(logn+logm)
public boolean binarySearchMatrix(int[][] matrix, int target) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) return false;
int up=0, bot=matrix.length-1, mid=0;
while(up<=bot) {
mid=up+(bot-up)/2;
if(matrix[mid][0]==target) {
return true;
} else if(matrix[mid][0] < target) {
up=mid+1;
} else {
bot=mid-1;
}
}
if(matrix[mid][0] > target){
if(mid == 0){
return false;
}
mid--;//mid-1
}
int row=mid;
// Manually write the binary search
/**
int l=0, r=matrix[l].length-1, row=mid;
while(l<=r) {
mid=l+(r-l)/2;
if(matrix[row][mid] == target) {
return true;
} else if(matrix[row][mid] < target) {
l=mid+1;
} else {
r=mid-1;
}
}
*/
// Used binary search api in java
return Arrays.binarySearch(matrix[row], target)>=0;
}