解題代碼:
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列的元素開始，若目标數字比該數字大，則向下比較，若目标數字比它小，則向左比較，直至超出矩陣的範圍，則可确定不存在該數字，若存在，必然會遇見。