剑指Offer[11]-旋转数组的最小数字

题目

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

python代码

class Solution(object):
    def minArray(self, numbers):
        len_n = len(numbers)
        if len_n==1:
            return numbers[0]
        for i in range(len_n-1):
            if numbers[i]>numbers[i+1]:
                return numbers[i+1]
        return numbers[0]

我们结合题目中描述的数组的特点,会发现,我们只要找出第一个符合其值小于左侧值的元素即为最小值。上述的方法很容易想到,按照我们发现的规律,我们只需遍历一次数组,就可把最小值找出来,时间复杂度为O(n)。

拓展

还有优化的空间吗?当遇到“有序数组”中查询元素这个问题,我们会立马想到二分法(时间复杂度O(logn)),那这道题可以使用二分思想来解决吗?

我们先简单分析一下可行性,我们假定数组为arr,a=0,b=len(arr)-1, m=(a+b)//2

  • 当arr[m] > arr[b]时,说明m落在了左侧有序片段。
  • 当arr[m] < arr[b]时,说明m落在了右侧有序片段。
  • 当arr[m] = arr[b]时,此时我们无法直接判断m处于哪侧。
    • 假设m落在右侧有序片段,类似[1,1,0,1,1,1,1,1,1]
    • 假设m落在左侧有序片段,类似[1,1,1,1,1,1,0,1,1]
    • 我们发现此时并不能继续使用二分法了,此时方法会退化为第一种的思路,我们只能利用最原始的条件,最小值一定在b的左侧,所以我们只需b=b-1,直到b遇到最小值或m找到最小值。
class Solution(object):
    def minArray(self, numbers):
        len_n = len(numbers)
        if len_n==1:
            return numbers[0]
        a = 0
        b = len_n-1
        while a!=b:
            m = (a+b)//2
            if numbers[m] > numbers[b]:
                a = m+1
            elif numbers[m]<numbers[b]:
                b = m
            else:
                b -= 1
        return numbers[a]

发表评论

电子邮件地址不会被公开。