剑指 Offer 11. 旋转数组的最小数字

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

题目

把一个数组最开始的若干个元素搬到数组的开端，咱们称之为数组的旋转。输出一个递增排序的数组的一个旋转，输入旋转数组的最小元素。例如，数组 [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

留神：本题与主站 154 题雷同：https://leetcode-cn.com/probl…

解题思路

思路：二分查找

先审题，反复一下【旋转数组】的概念。在这里，旋转数组指的是将升序排列数组的后面若干个元素放到数组开端。

那么，依照这个概念，咱们能够发现。数组旋转后，会将原数组 nums 拆分成两个升序排序的数组，设为 nums1、nums2，而且被搁置在开端局部的数组 nums2 的元素会小于或等于后面局部的数组 nums1 的元素（这里会呈现等于，是因为元素可能反复，待会再剖析）。那么当初的问题就是如何找到旋转后两个升序的数组？因为只有找到旋转后的两个数组，nums2 数组中的首元素就是要求的答案。

那么，在这里，咱们能够思考应用二分查找的办法，找到一个分界点（这个分界点为搁置在开端升序数组的首元素），分界点右边的数组为 nums1，分界点左边（含分界点）的数组为 nums2。

具体的思路如下（上面内容中，呈现 nums1 示意旋转后右边升序数组，nums2 示意旋转后搁置开端的左边升序数组）：

• 首先，定义指针 left,right 别离指向 nums 数组的首尾两端，而 mid 为每次二分查找的中点；

• 开始进行比拟（nums1 的元素大于或等于 nums2 的元素 ），这里会呈现以下三种状况：

  • 如果 nums[mid] > nums[right] 时，那么 mid 肯定是 nums1 这个数组当中，此时分界点落在区间 (mid, right]，令 left=mid+1；
  • 如果 nums[mid] < nums[right] 时，那么 mid 则在 nums2 数组当中，此时分界点落在区间 [left, mid]，令 right=mid;
  • 如果 nums[mid] == nums[right]（这里是因为容许元素反复），这里就会呈现边界含糊的状况，先说论断（前面剖析），让 right 指针往前挪动，令 right -= 1。

这里就 nums[mid] == nums[right] 的状况进行剖析，假如给定数组为 [1, 1, 0, 1] 和 [1, 0, 1, 1, 1]，那么会有如下的状况

• 当给定数组 [1, 1, 0, 1]，针对这种状况，left = 0, right = 3, mid = 1：

  • nums[mid] == nums[right]，这个时候 mid 在右边的数组 nums1 中。

• 当给定数组 [1, 0, 1, 1, 1]，此时 left = 0, right = 4, mid = 2：

  • nums[mid] == nums[right]，但此时 mid 在左边的数组 nums2 中。

在这里，无奈直接判断 mid 落在 nums1 还是 nums2 中。在后面中给出论断，令 right -= 1 来解决这个问题，依据下面剖析可能呈现的状况，当初剖析这个论断可行性：

• 当 mid 落在 nums1 数组中，因为 nums1 的任一元素大于或等于 nums2 中的元素，也就是说（设分界点为 point）nums[point] <= nums[mid] == nums[right]，那么：

  • 若 nums[point] < nums[right] 时，这里阐明 right 左侧的元素还有小值，令 right -= 1 后，point 还是在 [left, right] 这个区间当中；
  • 如果 nums[point] == nums[right] 时，这里要留神分界点索引 point 与 right 相等的状况。这个时候，令 right-=1，此时 point 将不在 [left, right] 这个区间当中。假如有如下的数组 [1, 1, 2, 1]，在这里 left = 0, right = 3, mid = 1，咱们能够看到分界点就是最初的那个 1。此时 point == right，若令 right -= 1，那么这里最初的 1 将会被抛弃。然而最终后果还是会返回 1，因为舍弃最初的 1 后，持续二分查找，分界点肯定会落在 [left, mid] 中，而且这个区间的元素值都等于 nums[point]。所以可能返回正确值。
• 当 mid 落在 nums2 数组中，也就是说 [mid, right] 这个区间的所有元素值都是相等的。此时令 right -= 1 只是舍弃一个反复值，而 point 还是落在 [left, right] 这个区间当中。

以下是算法实现的图解：

具体实现代码如下。

代码实现

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left = 0
        right = len(numbers) - 1

        while left < right:
            # 取中点
            mid = left + (right - left) // 2
            # 如果 numbers[mid] > numbers[right] , 分界点落在 (mid, right]
            if numbers[mid] > numbers[right]:
                left = mid + 1
            # numbers[mid] < numbers[right]，分界点落在 [left, mid]
            elif numbers[mid] < numbers[right]:
                right = mid
            # numbers[mid] == numbers[right]，令 right-=1，此论断可行性已在文章进行剖析
            else:
                right -= 1

        return numbers[left]

实现后果

欢送关注

公众号【书所集录】