1.
设查找的数位y，第一行最后一列的数位x
如果x<y，x是第一行最大的，所以第一行都小于y，删除第一行；
如果x>y，x是最后一列最小的，所以最后一列都大于y，删除最后一列；
这样保证x永远在可能有解的矩阵的第一行，最后一列。
时间复杂度：O（m＋n）
class Solution {
public:
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
bool searchMatrix(vector<vector<int> > &matrix, int target) {
// write your code here
int m = matrix.size();
if (m == ) {
return false;
}
int n = matrix[].size();
int r = , c = n - ;
while (r < m && c >= ) {
if (matrix[r][c] < target) {
r++;
} else if (matrix[r][c] > target) {
c--;
} else {
return true;
}
}
return false;
}
};
2. 分治法1
设查找的数位y，取中心点x，把矩阵分解成4部分
如果x<y，x是A中最大的，所以A都小于y，删除A；
如果x>y，x是D中最小的，所以D都小于y，删除D；
A ｜ B
————
C ｜ D
时间复杂度：O(N) = O(N/4)+O(N/2)+O(1), 介于O(N^0.5)~O(N)之间
class Solution {
public:
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
bool helper(vector<vector<int> > &M, int x1, int y1, int x2, int y2, int target) {
if (x1 > x2 || y1 > y2) {//empty matrix
return false;
}
int midx = (x1 + x2)>>;
int midy = (y1 + y2)>>;
if (M[midx][midy] == target) {
return true;
}
return (M[midx][midy] > target)?
(helper(M, x1, y1, x2, midy-, target)||helper(M, x1, midy, midx-, y2, target)):
(helper(M, x1, midy+, x2, y2, target)||helper(M, midx+, y1, x2, midy, target));
}
bool searchMatrix(vector<vector<int> > &matrix, int target) {
// write your code here
int m = matrix.size();
if (m == ) {
return false;
}
int n = matrix[].size();
return helper(matrix, , , m - , n - , target);
}
};
3. 分治法2
设查找的数为y，在中线找到这样两个数x1，x2，使得x1<y,x2>y，把矩阵分成4部分
A｜ B
————
C｜ D
x1是A中最大的，所以A都小于y，删掉A；
x2是D中最小的，所以D都大于y，删掉D；
时间复杂度：O(N)＝2O(N/4)+O(logn), 为O(N^0.5)
class Solution {
public:
/**
* @param A, a list of integers
* @param left, an integer
* @param right, an integer
* @param target, an integer
* @return an integer, indicate the index of the last number less than or equal to target in A
*/
int binarySearch(vector<int> &A, int left, int right, int target) {
while (left <= right) {//not an empty list
int mid = (left + right) >> ;
if (A[mid] <= target) {
left = mid + ;//left is in the integer after the last integer less than or equal to target
} else {
right = mid - ;
}
}
return left - ;
}
/**
* @param M, a list of lists of integers
* @param x1, an integer
* @param y1, an integer
* @param x2, an integer
* @param y2, an integer
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
bool helper(vector<vector<int> > &M, int x1, int y1, int x2, int y2, int target) {
if (x1 > x2 || y1 > y2) {//empty matrix
return false;
}
int midx = (x1 + x2)>>;
int indy = binarySearch(M[midx], y1, y2, target);
//M[midx][indy] <= target
if ((indy >= y1) && (M[midx][indy] == target)) {
return true;
}
return (helper(M, x1, indy+, midx-, y2, target))||(helper(M, midx+, y1, x2, indy, target));
}
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
bool searchMatrix(vector<vector<int> > &matrix, int target) {
// write your code here
int m = matrix.size();
if (m == ) {
return false;
}
int n = matrix[].size();
return helper(matrix, , , m - , n - , target);
}
};