题目描述：

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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Python代码：

class Solution:
# @param {integer[][]} matrix
# @param {integer} target
# @return {boolean}
def searchMatrix(self, matrix, target):
y = len(matrix[0]) - 1
for x in range(len(matrix)):
while y and matrix[x][y] > target:
y -= 1
if matrix[x][y] == target:
return True
return False

Python代码：

class Solution:
# @param {integer[][]} matrix
# @param {integer} target
# @return {boolean}
def searchMatrix(self, matrix, target):
y = len(matrix[0]) - 1
def binSearch(nums, low, high):
while low <= high:
mid = (low + high) / 2
if nums[mid] > target:
high = mid - 1
else:
low = mid + 1
return high
for x in range(len(matrix)):
y = binSearch(matrix[x], 0, y)
if matrix[x][y] == target:
return True
return False

Java代码：

public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n=matrix.length, m=matrix[0].length;
return helper(matrix,0,n-1,0,m-1,target);
}
boolean helper(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd, int target ){
if(rowStart>rowEnd||colStart>colEnd){
return false;
}
int rm=(rowStart+rowEnd)/2, cm=(colStart+colEnd)/2;
if(matrix[rm][cm]== target){
return true;
}
else if(matrix[rm][cm] >target){
return helper(matrix, rowStart, rm-1,colStart, cm-1,target)||
helper(matrix,  rm, rowEnd, colStart,cm-1,target) ||
helper(matrix, rowStart, rm-1,cm, colEnd,target);
}
else{
return helper(matrix, rm+1, rowEnd, cm+1,colEnd,target)||
helper(matrix,  rm+1, rowEnd, colStart,cm,target) ||
helper(matrix, rowStart, rm,cm+1, colEnd,target);
}

}

Pingbacks已关闭。

1. fireisborn 发布于 2015年8月2日 23:29 #

第一個演算法不是應該是 O(m*n) 嗎？

2. 在线疯狂 发布于 2015年8月3日 17:02 #

再仔细思考一下，内循环的n是单调不增的 :)

3. 柯大咨 发布于 2015年12月26日 13:15 #

我也觉得第一个算法的复杂度是O(m*n);

4. 在线疯狂 发布于 2015年12月26日 17:42 #

可以说一下原因吗？

5. 柯大咨 发布于 2015年12月29日 11:56 #

不好意思，我理解错误了，仔细看了一下，应该是O(m+n)，

6. Tina 发布于 2016年6月5日 14:00 #

赞第一种算法，非常巧妙