题目描述

[EN | CN]

假设按照 升序排序 的数组在预先未知的某个点上进行了旋转。

例如,数组 [0, 1, 2, 4, 5, 6, 7] 可能变为 [4, 5, 6, 7, 0, 1, 2]

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

解法 1:二分法

简单的思路就是二分查找,每次都看数组中间的那个数,

  • 如果中间数小于数组开头,那么说明中间数所在的位置已经被 rotate 过了;
  • 如果中间数大于数组开头,那么说明中间数所在的位置还没有被 rotate 过。

这里还要考虑几个特殊情况:

  • 若数组的长度小于 3,那么直接返回数组的最小值;
  • 若数组没有经过 rotation(我也不知道为什么会不经过……),那么返回数组开头的值。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(\log n)$,二分查找嘛;
  • 空间复杂度为 $O(n)$,第一次切就需要 $\frac{n}{2}$ 的空间……递归的时候不应该传新的数组进去的,应该传原数组和指针,罪过罪过,下一个解法把这里优化掉。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] < nums[-1]:
            return nums[0]

        if len(nums) <= 2:
            return min(nums)

        m_idx = int(len(nums) / 2)

        if nums[m_idx] < nums[0]:
            if nums[m_idx] < nums[m_idx - 1]:
                return nums[m_idx]
            return self.findMin(nums[:m_idx])
        else:
            if nums[m_idx] > nums[m_idx + 1]:
                return nums[m_idx + 1]
            return self.findMin(nums[m_idx + 1:])
  • Runtime: 36 ms, faster than 99.15% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
  • Memory Usage: 13 MB, less than 100.00% of Python3 online submissions for Find Minimum in Rotated Sorted Array.

解法 2:二分法(两指针)

跟解法 1 的思路一样,不过在递归的时候通过传原数组和两个指针指示 leftright,从而避免了 $O(n)$ 空间复杂度。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(\log n)$;
  • 空间复杂度为 $O(1)$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] < nums[-1]:
            return nums[0]

        def findMin_helper(nums, left, right):
            if right - left <= 1:
                return min([nums[left], nums[right]])

            m_idx = int((left + right + 1) / 2)

            if nums[m_idx] < nums[left]:
                if nums[m_idx] < nums[m_idx - 1]:
                    return nums[m_idx]
                return findMin_helper(nums, left, m_idx - 1)

            else:
                if nums[m_idx] > nums[m_idx + 1]:
                    return nums[m_idx + 1]
                return findMin_helper(nums, m_idx + 1, right)

        return findMin_helper(nums, 0, len(nums) - 1)
  • Runtime: 28 ms, faster than 100.00% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
  • Memory Usage: 13.1 MB, less than 96.00% of Python3 online submissions for Find Minimum in Rotated Sorted Array.