ps如何做网站专题,网站页面和图片设计,h5case 网站,商城网站建设的步骤Python算法题集_搜索旋转排序数组 题33#xff1a;搜索旋转排序数组1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【二分法区间判断】2) 改进版一【二分找分界标准二分法】3) 改进版二【递归实现二分法】 4. 最优算法5. 相关资源 本文为Pytho… Python算法题集_搜索旋转排序数组 题33搜索旋转排序数组1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【二分法区间判断】2) 改进版一【二分找分界标准二分法】3) 改进版二【递归实现二分法】 4. 最优算法5. 相关资源 本文为Python算法题集之一的代码示例
题33搜索旋转排序数组
1. 示例说明 整数数组 nums 按升序排列数组中的值 互不相同 。 在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1 输入nums [4,5,6,7,0,1,2], target 0
输出4示例 2 输入nums [4,5,6,7,0,1,2], target 3
输出-1示例 3 输入nums [1], target 0
输出-1提示 1 nums.length 5000-104 nums[i] 104nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转-104 target 104 2. 题目解析
- 题意分解
本题是将已排序列表旋转一次后从中查找目标数值最快方式就是二分法原理是每次二分后检查左右边界以[4,5,6,7,0,1,2]为例左区间和右区间中左边界小于等于target或者右边界大于等于target则target就在这个区间中
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 老实说二分法速度太快评估速度性能优点难标准算法就是题意分解解法 可以先找旋转的位置就是原本nums[0]的位置然后判断target在哪个区间后用标准二分法求解 可以考虑用递归法来实现二分法
- 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】因此需要本地化测试解决数据波动问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题本地化超时测试用例自己生成详见章节【最优算法】代码文件包含在【相关资源】中 3. 代码展开
1) 标准求解【二分法区间判断】
二分法查询区间左右边界和target
页面功能测试性能一般超过74%
import CheckFuncPerf as cfpclass Solution:def search_base(self, nums, target):ileft 0iright len(nums)while ileft iright:imid ileft ((iright - ileft) // 2)if nums[imid] target:return imidif nums[ileft] nums[imid]:if nums[ileft] target and target nums[imid]:iright imidelse:ileft imid 1else:if nums[imid] target and target nums[iright - 1]:ileft imid 1else:iright imidreturn -1aSolution Solution()
result cfp.getTimeMemoryStr(aSolution.searchRange_base, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 search_base 的运行时间为 0.00 ms内存使用量为 136.00 KB 执行结果 866666672) 改进版一【二分找分界标准二分法】
先用二分法查询原始nums[0]的下标然后用标准二分法在有序数值中查找target
页面功能测试惨不忍睹超过14%
import CheckFuncPerf as cfpclass Solution:def search_ext1(self, nums, target):if len(nums) 1:if nums[0] target:return 0else:return -1def base_search(nums, ileft, iright, itarget):while ileft iright:imid ileft (iright - ileft) // 2if nums[imid] itarget:ileft imid 1elif nums[imid] itarget:iright imid - 1else:return imidreturn -1pos_div 0ileft, iright 0, len(nums) - 1while ileft iright:imid ileft (iright - ileft) // 2if imid 0 and nums[imid] nums[imid - 1]:pos_div imidbreakif nums[ileft] nums[imid] and nums[imid] nums[iright]: # right is disorderedileft imid 1else:iright imid - 1pos_div ileftif nums[len(nums) - 1] target nums[pos_div]:return base_search(nums, pos_div, len(nums) - 1, target)else:return base_search(nums, 0, pos_div - 1, target)aSolution Solution()
result cfp.getTimeMemoryStr(aSolution.search_ext1, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 search_ext1 的运行时间为 0.00 ms内存使用量为 4.00 KB 执行结果 866666673) 改进版二【递归实现二分法】
使用递归函数来实现二分法另类做法
页面功能测试性能一般超过81%
import CheckFuncPerf as cfpclass Solution:def search_ext2(self, nums, target):def find_target(listnums, ileft, iright, itarget):mid (ileft iright) // 2if ileft iright:return -1if ileft 1 iright:if listnums[ileft] itarget:return ileftelif listnums[iright] itarget:return irightelse:return -1if listnums[ileft] listnums[mid]:if itarget listnums[ileft] and itarget listnums[mid]:result find_target(listnums, ileft, mid, itarget)else:result find_target(listnums, mid 1, iright, itarget)else:if itarget listnums[mid] and itarget listnums[iright]:result find_target(listnums, mid, iright, itarget)else:result find_target(listnums, ileft, max(mid - 1, 0), itarget)return resultreturn find_target(nums, 0, len(nums) - 1, target)aSolution Solution()
result cfp.getTimeMemoryStr(aSolution.search_ext1, nums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 search_ext1 的运行时间为 0.00 ms内存使用量为 4.00 KB 执行结果 866666674. 最优算法
根据本地日志分析本题怎么玩只要是二分法指标都差不多
import random
ilen, istart 10000, 0
nums [0 for x in range(ilen)]
for iIdx in range(ilen):istart random.randint(1, 3)nums[iIdx] istart
ipos, itarget ilen//3, nums[ilen // 5]
checknums nums[ipos:]
checknums.extend(nums[:ipos])
aSolution Solution()
result cfp.getTimeMemoryStr(aSolution.search_base, checknums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))
result cfp.getTimeMemoryStr(aSolution.search_ext1, checknums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))
result cfp.getTimeMemoryStr(aSolution.search_ext2, checknums, itarget)
print(result[msg], 执行结果 {}.format(result[result]))# 算法本地速度实测比较
函数 search_base 的运行时间为 0.00 ms内存使用量为 136.00 KB 执行结果 86666667
函数 search_ext1 的运行时间为 0.00 ms内存使用量为 4.00 KB 执行结果 86666667
函数 search_ext2 的运行时间为 0.00 ms内存使用量为 84.00 KB 执行结果 866666675. 相关资源
本文代码已上传到CSDN地址Python算法题源代码_LeetCode(力扣)_搜索旋转排序数组
一日练一日功一日不练十日空
may the odds be ever in your favor ~
