面试题11. 旋转数组的最小数字【中高难】

题目描述

做题链接：面试题11. 旋转数组的最小数字【中高难】

把一个数组最开始的若干个元素搬到数组的末尾，例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

解题思路

本题不难，但是需要考虑的情况很多，编的时候出了很多问题，故标记为 中高难度

方法：变形二分查找

时间复杂度O(n) 空间复杂度 O(1)

变形的二分查找，但是有一些坑

a. 正确情况下的二分查找

b. 特殊情况

当出现重复数字情形的时候，直接缩小左边界（因为最小值总是在右侧出现）

情形4 可以适应非递增数列的最小值为队首元素的情形。最后的代码非常巧妙

• 二分法解题需要考虑的情况

  • while left <= right 是错误的

  实例：[2,2,2,0,1]

  错误输出 2 ，实际上是 0

  • right = mid 提现了最小值一般是在右侧

  • 考虑到存在有序的情况，单独处理

方法二：直接搜索

直接搜索 左边大于右边的点

• 如果数组空，范围0
• 如果找到左边大于右边的点， 返回
• 没有找到，证明有序，返回 头结点

代码

方法一：二分法

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        left = 0
        right = len(rotateArray) - 1
        while left < right: # 不能是 <=
            # 加入特殊情况，非递减数组的最小值就是队首
            if rotateArray[left] < rotateArray[right]:
                return rotateArray[left]
            mid = (left + right) // 2 
            if rotateArray[mid] > rotateArray[left]:
                 left = mid + 1  # 一般都是在右侧，所以放心加1
            elif rotateArray[mid] < rotateArray[right]:
                 right = mid # 此时 mid 可能是最小值，不能排除
            else:
                 left += 1  # 巧妙避免了offer书上说的坑点（1 0 1 1 1）
        return rotateArray[left]

方法二：直接搜索

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
       
        for i in range(1, len(rotateArray)):
            if rotateArray[i-1] > rotateArray[i]:
                return rotateArray[i]
        return rotateArray[0]