讲真这题ac太快，我觉得有点简单，所以别人的方法应该会比我的好。不管怎样，先记下我的代码：
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
i = 0
while i < m:
if target >= matrix[i][0]:
i += 1
else:
break
if i == 0:
return False
else:
if matrix[i-1][n-1] < target:
return False
else:
flag = False
for j in range(n):
if matrix[i-1][j] == target:
flag = True
break
return flag
突然就想起来剑指offer上的一道题目，按照那一题的做法，代码如下：
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
col = n - 1
row = 0
while row < m and col >= 0:
if matrix[row][col] == target:
return True
if matrix[row][col] > target:
col -= 1
else:
row += 1
return False
事实证明这道题确实有特别多的解法，因为矩阵的特性可以将其看作是一个一维数组，因此用一维数组的办法来做这一题，代码如下：
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
#一维数组的办法
res = []
for i in matrix:
res += i
start = 0
end = len(res) - 1
while start <= end:
mid = (start + end) / 2
if res[mid] == target:
return True
elif res[mid] < target:
start = mid + 1
else:
end = mid - 1
return False
其实不用特意构造一个一维数组，可以直接通过下标来表示，上面的方法比较笨，下面是改良版本的，代码如下：
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
#一维数组的办法
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
start = 0
end = m * n - 1
while start <= end :
mid = (start + end) / 2
r = mid / n
c = mid % n
if matrix[r][c] == target:
return True
elif matrix[r][c] < target:
start = mid + 1
else:
end = mid - 1
return False
两次二分查找的办法，先按照行进行查找，不过这里情况要复杂一些，因为还要考虑到，虽然大于行首的数字但还是有可能在这一行，因此判断不在这一行的办法就是头和尾都小于target或者头部大于target，因此如果头部小于target 尾部大于target 很有可能就在这一行就需要break，当然判断是否等于mid,也是要头部或者尾部的。代码如下：
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
#一维数组的办法
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
start = 0
end = m - 1
mid = 0
while start <= end:
mid = (start + end) / 2
if matrix[mid][0] == target or matrix[mid][n-1] == target:
return True
elif matrix[mid][0] < target and matrix[mid][n-1] > target:
break
elif matrix[mid][0] > target:
end = mid - 1
else:
start = mid + 1
left = 0
right = n - 1
while left <= right:
mid2 = (left + right) / 2
if matrix[mid][mid2] == target:
return True
elif matrix[mid][mid2] < target:
left = mid2 + 1
else:
right = mid2 - 1
return False
这么看来上述这么多做法，虽然思想就几种，但是同一种思想做法也有好坏之分，总之，最上面的AC太快的可谓是暴力解法了。
