分类：BinarySearch
考察知识点：BinarySearch
最优解时间复杂度：O(log(n+m))原版/O(logn)改进版
最优解空间复杂度：O(1)
74. Search a 2D Matrix
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.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
代码：
BinarySearch方法1:
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix)==0 or len(matrix[0])==0 or matrix[0][0]>target or matrix[-1][-1]<target:
return False
list_new=[]
for each in matrix:
list_new+=each
start=0
end=len(list_new)-1
while end-start>1:
mid=(end-start)//2+start
if target==list_new[mid]:
return True
elif target<list_new[mid]:
end=mid
else:
start=mid
if list_new[start]==target:
return True
if list_new[end]==target:
return True
return False
BinarySearch方法2改进版:
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix)==0 or len(matrix[0])==0 or matrix[0][0]>target or matrix[-1][-1]<target:
return False
row=len(matrix)-1
while(matrix[row][0]>target):
row-=1
start=0
end=len(matrix[row])-1
while(end-start)>1:
mid=(end-start)//2+start
if matrix[row][mid]==target:
return True
elif matrix[row][mid]<target:
start=mid
else:
end=mid
if matrix[row][start]==target or matrix[row][end]==target:
return True
return False
讨论：
1.排序的，然后找数字，一看到这两个条件，那么肯定是用binary search!切记切记
2.改进的方法先判断每一行是否是比原来的大，然后再每一小行做BinarySearch就可以了
我真牛逼啊哈哈！
