1.
设查找的数位y,第一行最后一列的数位x
如果x<y,x是第一行最大的,所以第一行都小于y,删除第一行;
如果x>y,x是最后一列最小的,所以最后一列都大于y,删除最后一列;
这样保证x永远在可能有解的矩阵的第一行,最后一列。
时间复杂度:O(m+n)
1 class Solution { 2 public: 3 /** 4 * @param matrix, a list of lists of integers 5 * @param target, an integer 6 * @return a boolean, indicate whether matrix contains target 7 */ 8 bool searchMatrix(vector<vector<int> > &matrix, int target) { 9 // write your code here 10 int m = matrix.size(); 11 if (m == 0) { 12 return false; 13 } 14 int n = matrix[0].size(); 15 int r = 0, c = n - 1; 16 while (r < m && c >= 0) { 17 if (matrix[r][c] < target) { 18 r++; 19 } else if (matrix[r][c] > target) { 20 c--; 21 } else { 22 return true; 23 } 24 } 25 return false; 26 } 27 };
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)之间
1 class Solution { 2 public: 3 /** 4 * @param matrix, a list of lists of integers 5 * @param target, an integer 6 * @return a boolean, indicate whether matrix contains target 7 */ 8 bool helper(vector<vector<int> > &M, int x1, int y1, int x2, int y2, int target) { 9 if (x1 > x2 || y1 > y2) {//empty matrix 10 return false; 11 } 12 int midx = (x1 + x2)>>1; 13 int midy = (y1 + y2)>>1; 14 if (M[midx][midy] == target) { 15 return true; 16 } 17 return (M[midx][midy] > target)? 18 (helper(M, x1, y1, x2, midy-1, target)||helper(M, x1, midy, midx-1, y2, target)): 19 (helper(M, x1, midy+1, x2, y2, target)||helper(M, midx+1, y1, x2, midy, target)); 20 21 } 22 bool searchMatrix(vector<vector<int> > &matrix, int target) { 23 // write your code here 24 int m = matrix.size(); 25 if (m == 0) { 26 return false; 27 } 28 int n = matrix[0].size(); 29 return helper(matrix, 0, 0, m - 1, n - 1, target); 30 } 31 };
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)
1 class Solution { 2 public: 3 /** 4 * @param A, a list of integers 5 * @param left, an integer 6 * @param right, an integer 7 * @param target, an integer 8 * @return an integer, indicate the index of the last number less than or equal to target in A 9 */ 10 int binarySearch(vector<int> &A, int left, int right, int target) { 11 while (left <= right) {//not an empty list 12 int mid = (left + right) >> 1; 13 if (A[mid] <= target) { 14 left = mid + 1;//left is in the integer after the last integer less than or equal to target 15 } else { 16 right = mid - 1; 17 } 18 } 19 return left - 1; 20 } 21 /** 22 * @param M, a list of lists of integers 23 * @param x1, an integer 24 * @param y1, an integer 25 * @param x2, an integer 26 * @param y2, an integer 27 * @param target, an integer 28 * @return a boolean, indicate whether matrix contains target 29 */ 30 bool helper(vector<vector<int> > &M, int x1, int y1, int x2, int y2, int target) { 31 if (x1 > x2 || y1 > y2) {//empty matrix 32 return false; 33 } 34 int midx = (x1 + x2)>>1; 35 int indy = binarySearch(M[midx], y1, y2, target); 36 //M[midx][indy] <= target 37 if ((indy >= y1) && (M[midx][indy] == target)) { 38 return true; 39 } 40 return (helper(M, x1, indy+1, midx-1, y2, target))||(helper(M, midx+1, y1, x2, indy, target)); 41 42 } 43 /** 44 * @param matrix, a list of lists of integers 45 * @param target, an integer 46 * @return a boolean, indicate whether matrix contains target 47 */ 48 bool searchMatrix(vector<vector<int> > &matrix, int target) { 49 // write your code here 50 int m = matrix.size(); 51 if (m == 0) { 52 return false; 53 } 54 int n = matrix[0].size(); 55 return helper(matrix, 0, 0, m - 1, n - 1, target); 56 } 57 };