关于建设网站的图片素材,公司的网站建设与维护论文,河源建筑设计企业名录黄页,网站开发市场前景Python算法题集_在排序数组中查找元素的第一个和最后一个位置 题34#xff1a;在排序数组中查找元素的第一个和最后一个位置1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【二分法两次左边界】2) 改进版一【二分法左右边界】3) 改进版二【第三… Python算法题集_在排序数组中查找元素的第一个和最后一个位置 题34在排序数组中查找元素的第一个和最后一个位置1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【二分法两次左边界】2) 改进版一【二分法左右边界】3) 改进版二【第三方模块】 4. 最优算法5. 相关资源 本文为Python算法题集之一的代码示例
题34在排序数组中查找元素的第一个和最后一个位置
1. 示例说明 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1 输入nums [5,7,7,8,8,10], target 8
输出[3,4]示例 2 输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]示例 3 输入nums [], target 0
输出[-1,-1]提示 0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109 2. 题目解析
- 题意分解
本题是在已排序列表中查找目标数值的左边界和右边界最快方式就是二分法
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 可以通过查找左边界的方式执行查找目标的左边界查找目标1的左边界 可以通过查找左边界、右边界的方式执行 可以考虑使用排序列表操作模块bisect
- 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】因此需要本地化测试解决数据波动问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题本地化超时测试用例自己生成详见章节【最优算法】代码文件包含在【相关资源】中 3. 代码展开
1) 标准求解【二分法两次左边界】
二分法查询目标值左边界和目标1左边界
页面功能测试性能一般超过78%
import CheckFuncPerf as cfpclass Solution:def searchRange_base(self, nums, target):def searchbig(target: int) - int:ileft, iright 0, len(nums)while ileft iright:imid ileft ((iright - ileft) 1)if nums[imid] target:iright imidelse:ileft imid 1return irightistart searchbig(target - 1)if istart len(nums) or nums[istart] ! target:return [-1, -1]iend searchbig(target)return [istart, iend - 1]aSolution Solution()
result cfp.getTimeMemoryStr(aSolution.searchRange_base, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 searchRange_base 的运行时间为 0.00 ms内存使用量为 4.00 KB 执行结果 [33333333, 33333334]2) 改进版一【二分法左右边界】
二分法查询目标值左边界和右边界
页面功能测试马马虎虎超过56%
import CheckFuncPerf as cfpclass Solution:def searchRange_ext1(self, nums, target):result [-1, -1]def searchbymode(ileft, iright, modeflag):while ileft iright:imid (ileft iright) // 2if nums[imid] target:if modeflag:result[0] imidiright imid - 1else:result[1] imidileft imid 1elif nums[imid] target:iright imid - 1else:ileft imid 1searchbymode(0, len(nums) - 1, True)searchbymode(0, len(nums) - 1, False)return resultaSolution Solution()
result cfp.getTimeMemoryStr(aSolution.searchRange_ext1, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 searchRange_ext1 的运行时间为 0.00 ms内存使用量为 4.00 KB 执行结果 [33333333, 33333334]3) 改进版二【第三方模块】
使用排序列表操作模块bisect来查找左右边界
页面功能测试马马虎虎超过42%
import CheckFuncPerf as cfpclass Solution:def searchRange_ext2(self, nums, target):from bisect import bisect_left, bisect_rightileft bisect_left(nums, target)if ileft len(nums):return [-1, -1]if nums[ileft] ! target:return [-1, -1]if ileft len(nums)-1:return [ileft, ileft]if nums[ileft1] ! target:return [ileft, ileft]iright bisect_right(nums[ileft1:], target)return [ileft, ileftiright]aSolution Solution()
result cfp.getTimeMemoryStr(aSolution.searchRange_ext2, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 searchRange_ext2 的运行时间为 680.67 ms内存使用量为 4.00 KB 执行结果 [33333333, 33333334]4. 最优算法
根据本地日志分析最优算法为第1种方式【二分法两次左边界】、第2种方式【二分法左右边界】并列
本题测试数据似乎能推出以下结论
二分法查询性能非常夸张简直是瞬间定位【1亿的数组1毫秒定位】第三方模块的算法估计是进行了切片操作
import random
ilen, istart 100000000, 0
nums [0 for x in range(ilen)]
for iIdx in range(ilen):istart random.randint(0, 3)nums[iIdx] istart
itarget nums[ilen // 3]
aSolution Solution()
result cfp.getTimeMemoryStr(aSolution.searchRange_base, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))
result cfp.getTimeMemoryStr(aSolution.searchRange_ext1, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))
result cfp.getTimeMemoryStr(aSolution.searchRange_ext2, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))# 算法本地速度实测比较
函数 searchRange_base 的运行时间为 0.00 ms内存使用量为 4.00 KB 执行结果 [33333333, 33333334]
函数 searchRange_ext1 的运行时间为 0.00 ms内存使用量为 4.00 KB 执行结果 [33333333, 33333334]
函数 searchRange_ext2 的运行时间为 680.67 ms内存使用量为 4.00 KB 执行结果 [33333333, 33333334]5. 相关资源
本文代码已上传到CSDN地址Python算法题源代码_LeetCode(力扣)_在排序数组中查找元素的第一个和最后一个位置
一日练一日功一日不练十日空
may the odds be ever in your favor ~
