leetcode || 74、Search a 2D Matrix
來源：程序員人生 發布時間：2015-04-28 08:38:17 閱讀次數：3276次
problem：
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.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3,
return true.
Hide Tags
Array Binary
Search
題意：給定1個矩陣：每行遞增，每列遞增，查找target是不是在該矩陣中
thinking：
經典2分法的時間復雜度為 log（m）+log(n)=log（m*n）
（1）2分法查找鎖定target在矩陣的哪1行
（2）2分法查找target是不是在鎖定的那1行
code：
2分法：時間復雜度為log（m）+log(n)=log（m*n）
class Solution {
public:
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⑴);
if(index<0 || index>=m)
return false;
return binary_search_2(matrix[index],target,0,n⑴);
}
protected:
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⑴);
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個不錯的算法，時間復雜度為O（m+n）：
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int i = 0, j = matrix[0].size() - 1;
while (i < matrix.size() && j >= 0)
{
if (target == matrix[i][j])
return true;
else if (target < matrix[i][j])
j--;
else
i++;
}
return false;
}
};
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
