【Leetcode刷题Python】74. 搜索二维矩阵
2023-09-14 09:12:59 时间
1 题目
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
示例 2:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false
2 解析
(1)方法一
从右上角开始搜索
(2)方法二
二分查找,
3 Python实现
(1)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 方法二:从右上角开始搜索
m = len(matrix)
n = len(matrix[0])
i,j = 0,n-1
while i<m and j>=0:
cur = matrix[i][j]
if cur ==target :return True
elif cur<target: i+=1
else:j-=1
return False
(2)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 方法一:二分查找
m = len(matrix)
n = len(matrix[0])
l,r = 0,m*n
while l<r:
i,j = divmod((l+r)//2,n)
x = matrix[i][j]
if x<target:
l = i *n+j+1
elif x>target:
r = i*n+j
else:
return True
return False
相关文章
- Python怎么输入小数和整数_python输入非负整数
- python运行代码不成功_Python | PyCharm无法直接运行(Run)脚本
- Python每日一练(六)
- Python进制转换与ASCII转换
- php sigpipe,Python的SIGPIPE信号「建议收藏」
- python hashlib_Python hashlib模块实例使用详解
- 快速入门:Python简单实例100个(入门完整版)
- python判断linux中文件是否存在_Python判断文件是否存在的三种方法
- 【说站】python多行读写的操作
- 【说站】python如何处理文件
- 【说站】python查询键值对是否在字典的三个方法
- Python基础 – 使用别人代码的模块机制
- Python数组切片_python print数组
- h5 Python_python做h5网站
- python udp编程_Python核心编程
- python django 数据库_Apache+Mysql+PHP/Python简单项目
- python type error是什么意思_Python 报错 TypeError:’DoesNotExist’对象不可调用
- python使用opencv如何保存图片_OpenCV Python 保存图片
- 人生苦短,我用Python-手把手教你如何使用python写串口调试助手
- 新手学Python可行吗?需要什么基础?(新手学python可行吗?需要什么基础)
- 使用Python+VTK实现三维模型的显示和切割(面绘制)
- 一步一步学会在Linux上运行Python程序(linux运行python程序)
- 用Python简化Linux指令:从繁琐变简单(python运行linux命令)
- 什么是线程(多线程),Python多线程的好处(超级详细)
- 使用 Python 的 toolz 库开始函数式编程
- Python文件读写操作实例详解
- python中使用sys模板和logging模块获取行号和函数名的方法
- python中正则表达式的使用详解
- Python的另外几种语言实现