153. Find Minimum in Rotated Sorted Array

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Test Cases

1
2

class Solution:
    def findMin(self, nums: List[int]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([3,4,5,1,2], 1),
    ([4,5,6,7,0,1,2], 0),
    ([11,13,15,17], 11),
])
class Test:
    def test_solution(self, nums, expected):
        sol = Solution()
        assert sol.findMin(nums) == expected

Thoughts

还是二分搜索的逻辑。

看数组中间位置的元素值，如果比两端的值都大，那么应该去右半边（不含中间位置）继续搜索。如果比两端的值都小，应该去左半边（含中间位置）继续搜索。如果介于两端的值之间，那么左端点就是最小值。

当子数组缩短到不超过 2 个元素的时候就可以停止，最后的一个元素，或者最后两个元素的较小值，就是整个数组的最小值。这样写代码的时候可以简化边界值的处理（运行速度也是更快的）。

时间复杂度 O(log n)，空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r - 1:
            m = (l + r) >> 1
            if nums[l] < nums[r]:
                return nums[l]
            elif nums[l] < nums[m]:
                l = m + 1
            else: # nums[m] < nums[r]
                r = m

        return min(nums[l], nums[r])

参考资料

• 反向引用

  • 33. Search in Rotated Sorted Array

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章