Python算法题集_寻找旋转排序数组中的最小值

本文为Python算法题集之一的代码示例

题153：寻找旋转排序数组中的最小值

1. 示例说明

• 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

  注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

  给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

  你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

  示例 1：

  输入：nums = [3,4,5,1,2]
  输出：1
  解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
  

  示例 2：

  输入：nums = [4,5,6,7,0,1,2]
  输出：0
  解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
  

  示例 3：

  输入：nums = [11,13,15,17]
  输出：11
  解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
  

  提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

2. 题目解析

- 题意分解

1. 本题是将值不重复的升序列表旋转n次后【未知】，从中查找最小数值，也就是原始的nums[0]
2. 每旋转一次就是将最大元素移动到左边界，比如[1,2,3,4,5,6,7]变成[7,1,2,3,4,5,6]
3. 最快方式就是二分法，原理是每次二分后检查左右边界，以[4,5,6,7,0,1,2]为例，左区间和右区间中，左边界小于等于target或者右边界大于等于target则target就在这个区间中

- 优化思路

1. 通常优化：减少循环层次

2. 通常优化：增加分支，减少计算集

3. 通常优化：采用内置算法来提升计算速度

4. 分析题目特点，分析最优解

   1. 老实说，二分法速度太快，评估速度性能优点难，标准算法就是二分法

   2. 可以考虑数组的内置函数

- 测量工具

• 本地化测试说明：LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】，因此需要本地化测试解决数据波动问题
• CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块
• 本题本地化超时测试用例自己生成，详见章节【最优算法】，代码文件包含在【相关资源】中

3. 代码展开

1) 标准求解【二分法+左边界】

二分法，左边界逼近到最小值

页面功能测试，马马虎虎，超过61%

import CheckFuncPerf as cfp

class Solution:
 def findMin_base(self, nums):
     pos_min = 0
     ileft, iright = 0, len(nums) - 1
     while ileft < iright:
         imid = ileft + (iright - ileft) // 2
         if nums[imid] <= nums[iright]:
             iright = imid
         else:
             ileft = imid + 1
         pos_min = ileft
     return nums[pos_min]

aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.findMin_base, checknums)
print(result['msg'], '执行结果 = {}'.format(result['result']))
 
# 运行结果
函数 findMin_base 的运行时间为 1.00 ms；内存使用量为 228.00 KB 执行结果 = 1

2) 改进版一【二分法+右边界】

二分法，右边界逼近到最小值，去掉临时变量pos_min

页面功能测试，惨不忍睹，超过34%

import CheckFuncPerf as cfp

class Solution:
 def findMin_ext1(self, nums):
     ileft, iright = -1, len(nums) - 1
     while ileft + 1 < iright:
         imid = (ileft + iright) // 2
         if nums[imid] < nums[-1]:
             iright = imid
         else:
             ileft = imid
     return nums[iright]

aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.findMin_ext1, checknums)
print(result['msg'], '执行结果 = {}'.format(result['result']))
 
# 运行结果
函数 findMin_ext1 的运行时间为 0.00 ms；内存使用量为 0.00 KB 执行结果 = 1

3) 改进版二【数值内部函数】

使用数组二次函数实现查找，一行代码实现

页面功能测试，马马虎虎，超过48%

import CheckFuncPerf as cfp

class Solution:
 def findMin_ext2(self, nums):
     return min(nums)

aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.findMin_ext2, checknums)
print(result['msg'], '执行结果 = {}'.format(result['result']))
 
# 运行结果
函数 findMin_ext2 的运行时间为 1110.68 ms；内存使用量为 16.00 KB 执行结果 = 1

4. 最优算法

根据本地日志分析，本题怎么玩，只要是二分法，指标都差不多，所以第一方法和第二方法并列最优

本题测试数据，似乎能推出以下结论：

1. 数组的min方法不是二分法
2. 多一个变量导致计算增多，因此第二算法优于第一算法，不过差别可以忽略不计

import random
ilen, istart = 100000000, 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.findMin_base, checknums)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(aSolution.findMin_ext1, checknums,)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(aSolution.findMin_ext2, checknums)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 算法本地速度实测比较
函数 findMin_base 的运行时间为 1.00 ms；内存使用量为 228.00 KB 执行结果 = 1
函数 findMin_ext1 的运行时间为 0.00 ms；内存使用量为 0.00 KB 执行结果 = 1
函数 findMin_ext2 的运行时间为 1110.68 ms；内存使用量为 16.00 KB 执行结果 = 1

5. 相关资源

本文代码已上传到CSDN，地址：Python算法题源代码_LeetCode(力扣)_寻找旋转排序数组中的最小值

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~