解题代码:
74. Search a 2D Matrix
classSolution {
public:
boolsearchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size()==0||matrix[0].size()==0)
return false;
int m=matrix.size(),n=matrix[0].size();
if(target<matrix[0][0]||target>matrix[m-1][n-1])
return false;
if(target==matrix[0][0]||target==matrix[m-1][n-1])
return true;
int l=0,h=m*n-1,mid;
while(l<h-1){
mid=(h+l)/2;
if(matrix[mid/n][mid%n]==target)
return true;
else{
if(matrix[mid/n][mid%n]>target)
h=mid;
else
l=mid;
}
}
return false;
}
};
240. Search a 2D Matrix II
classSolution {
public:
boolsearchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size()==0||matrix[0].size()==0)
return false;
int m=matrix.size(),n=matrix[0].size();
int i=0,j=n-1;
while(i<m&&j>=0){
if(matrix[i][j]==target)
return true;
else{
if(matrix[i][j]>target)
j--;
else
i++;
}
}
return false;
}
};
解题思路:
两个题目要求找出矩阵中是否存在目标数字。
对于第一题，由于矩阵每一行递增，切每一行最后一个数都比下一行第一个数小，因此可以将矩阵视为把一个递增的数组分成的多段，因此可以利用二分法求目标数字所在位置。
而对第二题来说，每一行每一列都是递增的。对每一行都使用二分法查找虽然比起把矩阵都遍历一遍要简单，但相对还是比较复杂。我们经观察不难发现，对于m*n矩阵，从第0行第n-1列的元素开始，若目标数字比该数字大，则向下比较，若目标数字比它小，则向左比较，直至超出矩阵的范围，则可确定不存在该数字，若存在，必然会遇见。