【Leetcode刷题Python】剑指 Offer 04. 二维数组中的查找
2023-09-14 09:13:02 时间
1 题目
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 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]
]
给定 target = 5,返回 true。
给定 target = 20,返回 false。
2 解析
每一行列表是递增排序,则在每一行的列表中进行二分查找
三种方法
- 非递归二分查找
- 递归的二分查找
- 内置函数
3 Python实现
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 非递归,迭代二分查找
# def Bisearch(nums, target):
# l ,r = 0,len(nums)-1
# if target not in nums:
# return -1
# while l<=r:
# mid = (l+r)//2
# if nums[mid]==target:
# return mid
# elif nums[mid]<target:
# l = mid+1
# else:
# r =mid-1
# return -1
# 递归二分查找
def Bisearch(OrderedList, key, left , right):
if left > right:
return -1
mid = (left + right) // 2
if key == OrderedList[mid]:
return mid
elif key > OrderedList[mid]:
return Bisearch(OrderedList, key, mid + 1, right)
else:
return Bisearch(OrderedList, key, left, mid - 1)
for nums in matrix:
# 方法一:非递归
# idx = Bisearch(nums,target)
# 方法二:递归
idx = Bisearch(nums,target,0,len(nums)-1)
# 使用内置二分查找函数
# 方法三:
# import bisect
# idx = bisect.bisect_left(nums, target)
if -1<idx<len(nums) and nums[idx] ==target:
return True
return False
相关文章
- 【Python实战】python中含有中文字符无法运行
- Python 刷Leetcode题库,顺带学英语单词(38)
- 华为OD机试 - 最大股票收益(Java & JS & Python)
- Dataset之MNIST:MNIST(手写数字图片识别+ubyte.gz文件)数据集的下载(基于python语言根据爬虫技术自动下载MNIST数据集)
- 已解决2.Set PROTOCOL_BUFFERS_PYTHON_IMPLEMENTATION=python (but this will use pure-Python parsing and wi
- 〖Python零基础入门篇⑬〗 - Python中的列表
- 【LeetCode Python实现】34. 在排序数组中查找元素的第一个和最后一个位置(中等)
- 【LeetCode Python实现】33. 搜索旋转排序数组(中等)
- 【LeetCode Python实现】260. 只出现一次的数字 III(中等)
- 【LeetCode Python实现】386. 字典序排数(中等)
- Python编程:shelve模块-持久化python数据
- Python:ImportError: No module named
- Python使用技巧(五):快速解决安装python-lxml模块库报错问题并简单使用
- python里使用正则的finditer()函数
- 【Leetcode刷题Python】26. 删除有序数组中的重复项
- 【Leetcode刷题Python】33. 搜索旋转排序数组
- 【Leetcode刷题Python】34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)
- 【Leetcode刷题Python】53. 最大子数组和
- 【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
- 【Leetcode刷题Python】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
- 【Leetcode刷题Python】416. 分割等和子集
- 【Leetcode刷题Python】198. 打家劫舍
- python工具方法 18 labelme语义分割标注数据批量转换为png
- 【Python实战】 ---- python 实现 CSDN 的定时自动签到