【剑指Offer】旋转数组中的最小数字 解题报告（Python）

标签（空格分隔）： LeetCode

---

题目地址：https://www.nowcoder.com/ta/coding-interviews

题目描述：

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

Ways

方法一：

使用O(N/2)的时间复杂度实现。思想是最小数字出现的时候，其前面的数字一定比它大。

面试官肯定不满意。

# -*- coding:utf-8 -*-

class Solution:

    def minNumberInRotateArray(self, rotateArray):

        if len(rotateArray) == 0:

            return 0

        pre,cur = 0,rotateArray[0]

        i = 1

        while i < len(rotateArray) and cur >= pre:

            pre,cur = cur,rotateArray[i]

            i += 1

        return cur

方法二：

使用二分查找的方式。可以把时间复杂度降低到o(logn)。具体解析请看《剑指offer》的66页。

# -*- coding:utf-8 -*-

class Solution:

    def minNumberInRotateArray(self, rotateArray):

        p1, p2 = 0, len(rotateArray) - 1

        mid = p1

        while rotateArray[p1] >= rotateArray[p2]:

            if p2 - p1 == 1:

                mid = p2

                break

            mid = (p1 + p2) / 2

            if rotateArray[mid] == rotateArray[p1] and rotateArray[mid] == rotateArray[p2]:

                return self.minInOrder(rotateArray, p1, p2)

            if rotateArray[mid] >= rotateArray[p1]:

                p1 = mid

            elif rotateArray[mid] <= rotateArray[p2]:

                p2 = mid

        return rotateArray[mid]

    def minInOrder(self, nums, index1, index2):

        n1 = nums[index]

        for i in range(index1 + 1, index2):

            if n1 > nums[i]:

                return nums[i]

        return n1

Date

2018 年 3 月 9 日