题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

分析

按照一般的算法,要找到最小的数组元素,时间复杂度应该为$O(n)$级别.这里显然不应该用那么暴力的算法,否则就很无趣了.

最关键的是那个旋转点,如果找到旋转点,这题就解决了.

但是直觉上发现很难找到这个点…

大概还是需要自己设定算法吧.

我们假设过程A可以找到一个旋转数组arr的最小值.

现在要做的就是对过程A的拆解,我们跟着直觉这样做

  • 过程A_1: 将arr从中间均分为arr1和arr2
  • 过程A_2: 用过程A找到arr1和arr2的最小值,然后返回其中最小的.

我们分析一下过程A的复杂度,有
$$
f(A)=2f(\frac{A}{2})+O(1)
$$

容易知道,过程A的复杂度仍然为$O(n)$…fuck

不过从中我们可以发现这个过程和二分搜索有点像.

我们需要再找找arr1和arr2的关系.

如果那个最小元素在arr1中,那么arr2必然都是非递减的.在arr2中同理.

例如arr1=4,5,1和arr2=2,3中的情况.

容易发现

  • arr1的最后一个数肯定比arr2的第一个数小.
  • arr1的第一个数比arr2的最后一个数大

经过调试发现,那只是个例…

比如arr1=4,5,6和arr2=7,8,1的情况.在这里

  • arr1的最后一个数比arr2的小
  • arr1的第一个数比arr2的最后一个数大

这两个算例的本质区别在哪里呢?

第二个算例中arr1中是非递减的,而第一个则不是.

所以我们判断的标准应该为

  • 如果arr1中第一个元素小于最后一个元素,说明arr1是顺序的.
  • 如果arr2中第一个元素不小于最后一个元素,说明arr2不是顺序的,那么应该返回arr2中的最小值
  • 如果arr2中第一个元素小于最后一个元素,说明arr2是顺序的,那么有两种可能
    • arr1和arr2整体是顺序的,返回arr1第一个元素即可
    • arr2和arr1两个局部是顺序的,返回arr2第一个元素即可.

这样我们就可以将过程A再做一个改进了

  • 过程A_1: 将arr从中间均分为arr1和arr2
  • 过程A_2: 判断那个数在arr1还是arr2中
  • 过程A_3: 将过程A_2的数用过程A处理,返回最小值.

显然复杂度为$log(n)$,game over!

最后的代码为

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)==0:
            return 0
        if len(rotateArray)==2:
            return min(rotateArray)
        if len(rotateArray)==1:
            return rotateArray[0]
        r = len(rotateArray)//2
        arr1 = rotateArray[:r]
        arr2 = rotateArray[r:]
        if arr1[0]<=arr1[-1]:
            if arr2[0]>=arr2[-1]:
                return self.minNumberInRotateArray(arr2)
            else:
                return min(arr1[0],arr2[0])
        else:
            return self.minNumberInRotateArray(arr1)
赏

我很好奇