题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

思路

  • 从头到尾遍历一遍，时间复杂度是O(n)。

部分有序，可以考虑二分查找。

二分查找的思路：

  • l指向最左边，r指向末尾
  • 中间元素 m = （l + r) // 2，
  • if nums[m] > nums[l]，左半部分是有序的，最小值后半部分；
  • if nums[m] < nums[l]，最小值位于前半部分。
  • if nums[m] == nums[l]，则顺序查找，left += 1。

代码

  1. class Solution:
  2.     def minArray(self, numbers: List[int]) -> int:
  3.         left = 0
  4.         right = len(numbers) - 1
  6.         while left + 1 < right:
  7.             if numbers[right] > numbers[left]:
  8.                 # 这部分已经是有序的
  9.                 return numbers[left]
  11.             mid = left + (right - left) // 2 # equal // 2
  13.             if numbers[mid] > numbers[left]:
  14.                 # 前半部分是有序的, 查找区间在右边
  15.                 left = mid
  16.             elif numbers[mid] < numbers[left]:
  17.                 right = mid
  18.             else:
  19.                 # 相等，则顺序查找
  20.                 left += 1
  22.         return numbers[left] if numbers[left] < numbers[right] else numbers[right]