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.
算法分析:
1. 从头到尾遍历, 没有算法可言. 时间复杂度 O(m*n)
2. 先遍历行的最后个元素, 可以确定要search的行. 然后再遍历此行, 时间复杂度 O(m + n)
3. 把整个martrix 看成一个首尾相连的二维数组, 然后使用二分法. 时间复杂度 O(log(m*n))
4. 对行首元素使用二分法确定要search的行, 然后再对此行使用二分法. 时间复杂度 O(logm+logn)
本题是使用第4种算法.
Java:
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
if (row == 0) return false;
int column = matrix[0].length;
if (column == 0) return false;
int left = 0;
int right = row - 1;
int mid = 0;
int comp = 0;
while (left <= right) {
mid = left + (right - left) / 2;
comp = matrix[mid][0];
if (comp < target) left = mid + 1;
else if (comp > target) right = mid - 1;
else return true;
}
if (right < 0) return false;
int rowIndex = right;
left = 0;
right = column - 1;
while (left <= right) {
mid = left + (right - left) / 2;
comp = matrix[rowIndex][mid];
if (comp < target) left = mid + 1;
else if (comp > target) right = mid - 1;
else return true;
}
return false;
}
}
C++:
class Solution {
public:
bool searchMatrix(vector > &matrix, int target) {
int row = matrix.size();
if (row == 0) return false;
int column = matrix[0].size();
if (column == 0) return false;
int left = 0;
int right = row - 1;
int mid = 0;
int comp = 0;
while (left <= right) {
mid = left + (right - left) / 2;
comp = matrix[mid][0];
if (comp < target) left = mid + 1;
else if (comp > target) right = mid - 1;
else return true;
}
if (right < 0) return false;
int rowIndex = right;
left = 0;
right = column -1;
while (left <= right) {
mid = left + (right - left) / 2;
comp = matrix[rowIndex][mid];
if (comp < target) left = mid + 1;
else if (comp > target) right = mid - 1;
else return true;
}
return false;
}
};
Python:
class Solution:
# @param matrix, a list of lists of integers
# @param target, an integer
# @return a boolean
def searchMatrix(self, matrix, target):
row = len(matrix)
if (row == 0):
return False
column = len(matrix[0])
if (column == 0):
return False;
left = 0
right = row - 1
rowIndex = 0
while left <= right:
mid = left + (right - left) / 2
comp = matrix[mid][0]
if (comp > target):
right = mid - 1
elif (comp < target):
left = mid + 1
else:
return True
if (right == -1):
return False
print [left, mid, right]
rowIndex = right
left = 0
right = column - 1
while left <= right:
mid = left + (right - left) / 2
comp = matrix[rowIndex][mid]
if (comp > target):
right = mid - 1
elif (comp < target):
left = mid + 1
else:
return True
return False
继续查看有关 日志连载的文章
0个访客评论