剑指offer 旋转数组的最小数字

Posted on |

题目

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

方法

二分查找实现$O(n \log n)$

两个指针分别总是第一个和最后一个元素。

  • 如果确定旋转了n>0个元素，第一个元素总是大于或等于最后一个元素（循环条件）
  • 如果数组旋转了n=0个元素，则数组本身就是递增数组，最小元素就是第一个元素
  • 如果中间元素位于前面的递增子数组，则mid要大于或等于front，此时最小元素位于中间元素之后
  • 如果中间元素位于后面的递增子数组，则mid要小于或等于rear，此时最小元素应该位于中间元素的前面或自己本身
  • 如果两个指针指向的数字和中间元素相等，只能采用顺序查找的方法

第一个指针总是指向第一个递增子数组的元素，第二个指针总是指向第二递增子数组的元素。最终第一个指针指向第一个递增子数组的最后一个元素，第二个指针指向第二个递增子数组的第一个元素。两个指针相邻，第二个指针指向的元素就是最小元素。

  • 循环条件：数组中第一个元素总是大于或等于最后一个元素
  • 循环结束条件：第一个指针和第二个指针相邻，第二个指针指向的元素就是最小元素
  • 边界测试：输入数组是一个升序数组；只包含一个数字的数组
  • 难点：数组中可能存在重复的数字，数组可能旋转了0和数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)==0:
            return

        front,rear=0,len(rotateArray)-1
        # 排除将0个元素搬到数组后面的情况，第一个元素就是最小值，直接返回结果
        mid=front

        # 其他情况下，第一个元素要大于或等于最后一个元素
        while rotateArray[front]>=rotateArray[rear]:
            # 如果front和rear的距离是1,表明front指向第一个递增子数组的末尾，rear指向第二个递增子数组的开头
            # 第二个递增子数组的开头就是最小元素
            if rear-front==1:
                mid=rear
                break

            mid=(front+rear)//2
            # 当front、mid、rear指向的数值相等，无法判断，只能顺序查找
            if rotateArray[front]==rotateArray[rear] and rotateArray[mid]==rotateArray[rear]:
                return self.MinInOrder(rotateArray,front,rear)

            # 如果中间元素位于前面的递增子数组，则mid要大于或等于front，此时最小元素位于中间元素之后
            if rotateArray[mid]>=rotateArray[front]:
                front=mid
            # 如果中间元素位于后面的递增子数组，则mid要小于或等于rear，此时最小元素应该位于中间元素的前面或自己本身
            elif rotateArray[mid]<=rotateArray[rear]:
                rear=mid
        return rotateArray[mid]

    def MinInOrder(self,rotateArray,front,rear):
        result=rotateArray[front]
        for n in rotateArray[front+1:rear+1]:
            if result>n:
                result=n
        return result