剑指06-旋转数组的最小数字

Posted on | In |

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

  • 最小值左右的子序列都是递增的，可用二分查找。
  • 通过画出旋转后的数组大小的增长曲线，很容易看出二分点在左子序列还是在右子序列。
  • 某次迭代时元素比较少时，比如二分点是查询区间的左端，也就是只剩两个元素，可以直接给出结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        i, j = 0, len(rotateArray)-1
        while i < j:
            mid = (i+j)//2
            if i == mid:
                return min(rotateArray[i:j+1])
            if rotateArray[mid] <= rotateArray[j] and  rotateArray[mid] <= rotateArray[i]:
                j = mid
                continue
            if rotateArray[mid] >= rotateArray[j] and  rotateArray[mid] >= rotateArray[i]:
                i = mid
        return rotateArray[i]