[LeetCode 74] Search a 2D Matrix - Shuatiblog.com
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
http://blog.csdn.net/linhuanmars/article/details/24216235
http://blog.csdn.net/ever223/article/details/44514849
https://leetcode.com/discuss/68637/java-clear-solution
bool searchMatrix(vector<vector<int> > &matrix, int target) { int n = (int)matrix.size(); int m = (int)matrix[0].size(); --n; --m; while(n > 0 && matrix[n - 1][m] >= target) --n; while(m > 0 && matrix[n][m - 1] >= target) --m; return (matrix[n][m] == target); }
Count Negative in a 2D Sorted Matrix
Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,
Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]
a linear walk from top-right to bottom-left.
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
思路就是一句话：把二维数组当成一个有序数组，直接二分搜索。
时间复杂度：O(log(mXn))
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null || matrix.length==0 || matrix[0].length==0)
return false;
int m = matrix.length;
int n = matrix[0].length;
int start = 0;
int end = m*n-1;
while(start<=end){
int mid=(start+end)/2;
int midX=mid/n;
int midY=mid%n;
if(matrix[midX][midY]==target)
return true;
if(matrix[midX][midY]<target){
start=mid+1;
}else{
end=mid-1;
}
}
return false;
}
https://leetcode.com/discuss/10735/dont-treat-it-as-a-2d-matrix-just-treat-it-as-a-sorted-list
bool searchMatrix(vector<vector<int> > &matrix, int target) { int n = matrix.size(); int m = matrix[0].size(); int l = 0, r = m * n - 1; while (l != r){ int mid = (l + r - 1) >> 1; if (matrix[mid / m][mid % m] < target) l = mid + 1; else r = mid; } return matrix[r / m][r % m] == target; }
http://n00tc0d3r.blogspot.com/2013/05/search-2d-matrix.html
bool searchMatrix(vector<vector<int> > &matrix, int target) { int n = matrix.size(); int m = matrix[0].size(); int l = 0, r = m * n - 1; while (l != r){ int mid = (l + r - 1) >> 1; if (matrix[mid / m][mid % m] < target) l = mid + 1; else r = mid; } return matrix[r / m][r % m] == target; }
Why you might want to consider some other solution instead of this -
row_num * col_nummight cause overflow.- Also,
/and%are expensive operations.
http://n00tc0d3r.blogspot.com/2013/05/search-2d-matrix.html
public boolean searchMatrix(int[][] matrix, int target) {
// binary search to find the row
int low = 0, high = matrix.length - 1;
while (low < high) {
int mid = (low + high) / 2;
if (target == matrix[mid][0]) return true;
else if (target < matrix[mid][0]) high = mid - 1;
else if (target < matrix[mid+1][0]) { low = mid; break; }
else low = mid + 1;
}
// binary search to find the target
int row = low;
low = 0; high = matrix[row].length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (target == matrix[row][mid]) return true;
else if (target < matrix[row][mid]) high = mid - 1;
else low = mid + 1;
}
return false;
}
经典二分法的时间复杂度为 log（m）+log(n)=log（m*n）
（1）二分法查找锁定target在矩阵的哪一行
（2）二分法查找target是否在锁定的那一行
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int m=matrix.size();
int n=matrix[0].size();
int index=binary_search_1(matrix,target,0,m-1);
if(index<0 || index>=m)
return false;
return binary_search_2(matrix[index],target,0,n-1);
}
int binary_search_1(vector<vector<int> > &matrix, int target, int start, int end)
//锁定target所在行
{
if(start>=end)
return start;
int mid=(start+end)/2;
if(target>=matrix[mid][0]&&target<matrix[mid+1][0])
return mid;
else if(target<matrix[mid][0])
return binary_search_1(matrix,target,start,mid-1);
else
return binary_search_1(matrix,target,mid+1,end);
}
bool binary_search_2(vector<int> &a, int target, int start, int end)
//在锁定行中查找target
{
if(start>=end)
return a[start]==target;
int mid=(start+end)/2;
if(a[mid]==target)
return true;
else if(a[mid]<target)
return binary_search_2(a,target,mid+1,end);
else
return binary_search_2(a,target,start,mid-1);
}
http://www.cnblogs.com/springfor/p/3857959.htmlhttp://blog.csdn.net/linhuanmars/article/details/24216235
1 public boolean searchMatrix(int[][] matrix, int target) {
2 if(matrix == null || matrix.length==0 || matrix[0].length==0)
3 return false;
4 int low = 0;
5 int high = matrix.length-1;
6 while(low<=high){
7 int mid = (low+high)/2;
8 if(matrix[mid][0] == target)
9 return true;
10 else if(matrix[mid][0] > target)
11 high = mid-1;
12 else
13 low = mid+1;
14 }
15
16 int row = high; //当从while中跳出时，low指向的值肯定比target大，而high指向的值肯定比target小
17
18 if(row<0)
19 return false;
20
21 low = 0;
22 high = matrix[0].length-1;
23 while(low<=high){
24 int mid = (low+high)/2;
25 if(matrix[row][mid] == target)
26 return true;
27 else if(matrix[row][mid] > target)
28 high = mid-1;
29 else
30 low = mid+1;
31 }
32 return false;
33 }
2 if(matrix == null || matrix.length==0 || matrix[0].length==0)
3 return false;
4 int low = 0;
5 int high = matrix.length-1;
6 while(low<=high){
7 int mid = (low+high)/2;
8 if(matrix[mid][0] == target)
9 return true;
10 else if(matrix[mid][0] > target)
11 high = mid-1;
12 else
13 low = mid+1;
14 }
15
16 int row = high; //当从while中跳出时，low指向的值肯定比target大，而high指向的值肯定比target小
17
18 if(row<0)
19 return false;
20
21 low = 0;
22 high = matrix[0].length-1;
23 while(low<=high){
24 int mid = (low+high)/2;
25 if(matrix[row][mid] == target)
26 return true;
27 else if(matrix[row][mid] > target)
28 high = mid-1;
29 else
30 low = mid+1;
31 }
32 return false;
33 }
http://blog.csdn.net/ever223/article/details/44514849
static boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; //行数
int n = matrix[0].length; //列数
int up = 0;
int down = m - 1;
int left = 0;
int right = n;
//二分法查找所在行
while(up < down) {
int mid = (down + up) / 2;
if(matrix[mid][n - 1] > target) down = mid;
else if(matrix[mid][n - 1] < target) up = mid + 1;
else return true;
}
//二分法查找所在列
while(left < right) {
int mid = (left + right) / 2;
if(matrix[up][mid] > target) right = mid;
else if(matrix[up][mid] < target) left = mid + 1;
else return true;
}
return false;
}
X. 时间复杂度为O（m+n）https://leetcode.com/discuss/68637/java-clear-solution
The basic idea is from right corner, if the current number greater than target col - 1 in same row, else if the current number less than target, row + 1 in same column, finally if they are same, we find it, and return return.
public boolean searchMatrix(int[][] matrix, int target) {
int i = 0, j = matrix[0].length - 1;
while (i < matrix.length && j >= 0) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
j--;
} else {
i++;
}
}
return false;
}bool searchMatrix(vector<vector<int> > &matrix, int target) { int n = (int)matrix.size(); int m = (int)matrix[0].size(); --n; --m; while(n > 0 && matrix[n - 1][m] >= target) --n; while(m > 0 && matrix[n][m - 1] >= target) --m; return (matrix[n][m] == target); }
Count Negative in a 2D Sorted Matrix
Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,
Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]
a linear walk from top-right to bottom-left.
int countNegatives(int array[][], int size) {
int col = size - 1, row = 0;
int count = 0;
while(row < size && col >= 0) {
if(array[row][col] < 0 ) {
count = count + (col + 1);
row = row + 1;
}
else {
col = col - 1;
}
}
return count;
}