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

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

示例 1:


输入:[3,4,5,1,2]

输出:1

示例 2:


输入:[2,2,2,0,1]

输出:0

一解

排序后,返回第一个值(最小值):


class Solution:

    def minArray(self, numbers: List[int]) -> int:

        numbers.sort()

        return numbers[0]

  • 执行用时:32ms,在所有 Python3 提交中击败了 95.34% 的用户

  • 内存消耗:152MB,在所有 Python3 提交中击败了 42.91% 的用户

使用官方 api ,利用快排的时间复杂度为 O(nlogn) ,时间不理想,并且不符合出题人思路。

二解

使用二分法,时间复杂度为 O(logn)。

以 12345 为例

如果数组进行旋转,可以得到两个递增数组34512

34512

其中:

  • 3、4、5数组的每一个值都比1、2数组的大

  • 3、4、5数组在1、2数组的前面

设:

  • start:最左边位置

  • mid:中间位置

  • end:最右边位置

索引的值:mid > end

数组发生了旋转,并且 mid 处于大数组中,小数组一定在 mid 的右边,比如:

34512

索引的值:mid < start

数组发生了旋转,并且 mid 是小数组中的某些值,最小值一定是 mid 或者 mid 左边。

51234

其它情况

不确定 mid 的位置,直接缩小 start 和 end 范围。


class Solution:

    def minArray(self, numbers: List[int]) -> int:

        start, end = 0, len(numbers) - 1

        while end > start:

            # 防止超范围

            mid = start + (end - start) // 2

            if numbers[mid] > numbers[end]:

                start = mid + 1

            elif numbers[mid] < numbers[start]:

                end = mid

            else:

                end -= 1

        return numbers[start]

代码start + (end - start) // 2(start + end)//2表达数学思想相同,都是取中位数,但前者可以防止大数运算start + end,某些语言(Java) int类型有大小限制,start + end可能会超出int范围。

  • 执行用时:32ms,在所有 Python3 提交中击败了 95.34%的用户

  • 内存消耗:15MB,在所有 Python3 提交中击败了 79.49%的用户

关闭