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 };
