跳转至

153. 寻找旋转排序数组中的最小值#

问题描述#

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

 

示例 1：


输入：nums = [3,4,5,1,2]
输出：1

示例 2：


输入：nums = [4,5,6,7,0,1,2]
输出：0

示例 3：


输入：nums = [1]
输出：1

 

提示：

  • 1 <= nums.length <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数都是 唯一 的
  • nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转

解题思路#

数组无重复元素。

  • 如果 nums[-1] >= nums[0]，说明整个数组有序，此时直接返回 nums[0] 即可。
  • 否则，使用二分搜索，最小值是整个数组中唯一小于它前面位置的数
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def findMin(self, nums: List[int]) -> int:
        """数组无重复元素"""
        if nums[-1] >= nums[0]:  # 整个数组有序
            return nums[0]

        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] >= nums[0]:  # 在前半部分
                lo = mid + 1
            else:  # 在后半部分
                if nums[mid] < nums[mid - 1]:  # 最小值是唯一一个小于它前面位置的数
                    return nums[mid]
                hi = mid - 1
        return nums[lo]
测试数据
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
solution = Solution()

nums = [3, 4, 5, 1, 2]
assert solution.findMin(nums) == 1

nums = [4, 5, 6, 7, 0, 1, 2]
assert solution.findMin(nums) == 0

nums = [1]
assert solution.findMin(nums) == 1

nums = [1, 2, 3, 4]
assert solution.findMin(nums) == 1

print("PASS!")
返回顶部

在手机上阅读