大一在读 大数据管理与应用专业 欢迎交流
备战蓝桥杯 倒计时70天
目前主要学习Python算法与数据结构
算法人算法魂 算法题让我们敢于挑战自己做意想不到的事情
快来试试今天的每日一练吧 Python小伙伴
问题描述:
来感受一下Python的简洁：遍历法（比较慢）
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for i in matrix: if target in i:return True return False
遍历法优化加强版：大于右上角最后一个元素 下移 否则左移动 注意特殊情况i>len(matrix)-1
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: i=0 while matrix[i][-1]<target: i+=1 if i>len(matrix)-1:return False return True if target in matrix[i] else False
终极加强版：二分法（对上一种的再次优化）
我们不再通过遍历查找’右上角‘元素 而是通过二分法查找 再在内部进行二分
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m,n=len(matrix[0]),len(matrix) l,r=-1,len(matrix) while l+1<r: mid=(l+r)//2 if matrix[mid][-1]>=target:#r指向右上角大于等于target的编号 r=mid else: l=mid#l指向右上角小于target的元素 if r==len(matrix):return False#特殊情况 l1,r1=0,len(matrix[r])-1 while l1<=r1: mid1=(l1+r1)//2 if matrix[r][mid1]>target: r1=mid1-1 elif matrix[r][mid1]<target: l1=mid1+1 else: return True return False
效率一般 说明有时利用好Python内置的函数反而更快 不过这种思想要掌握
第一次二分查找时 二分写法利用了区域划分的写法
可以有效地防止出错 可以看我这篇博客 传送门！
https://blog.csdn.net/m0_62277756/article/details/122711847?spm=1001.2014.3001.5501
