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

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

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

• • 题目描述：
  • 示例：
  • 解题思路：
  • 代码：
  • • c++
    • python

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

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [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

解题思路：

可参考：Krahets & 作者：jyd.与官方解题方法。
》》》》》注意题干的条件：它原来是一个升序排列的数组《《《《《《

• 寻找最小元素即为寻找 右排序数组 的首个元素 nums[x] , 旋转点
• 利用二分查找的思想可以解题：

左边界为 low，右边界为high，区间的中点为 mid，最小值就在该区间内。将中间的元素 numbers[mid] 与右边界元素numbers[high] 进行比较，可能会有以下的三种情况：

1.当nums[mid] < nums[ high ]时：mid一定在右排序数组中，即旋转点x一定在**[ low，mid]**闭区间内，因此执行 high = mid ,缩小区间范围；

2.**当nums[mid] > nums[ high ]时：mid 一定在左排序数组中，即旋转点x一定在[mid+1，high]**闭区间内，因此执行 low=mid+1；

3.当nums[m] = nums[ high ]时：无法判断m在哪个排序数组中，即无法判断旋转点x在 [ low，mid ]还是[m+1，high]区间中。执行： high=high-1 缩小判断范围。

• 当 i=j 时跳出二分循环，并返回 旋转点的值 nums[ low] 就是最小值。

• 图示：(只看顺序，自己捋顺逻辑)
  
  
  
  
  

代码： c++

class Solution {
public:
    int minArray(vector& numbers) {
        int low =0;
        int high = numbers.size()-1;
        while (lownumbers[high] ){
                low = mid+1;
            }
            
            else if (numbers[mid] < numbers[high] ){
                high=mid;
            }
            
            else high--;
        }
        return numbers[low];

    }
};

python

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        low,high=0,len(numbers)-1;
        while low < high:
            mid = (low+high)//2;
            if numbers[mid] < numbers[high]:
                high = mid; 
            elif numbers[mid] > numbers[high]:
                low = mid +1;
            else:
                return min(numbers[low:high])
        return  numbers[low];

• 复杂度分析：
• 时间复杂度O（log2N）：在特例情况下（例如[1，1，1，1，1]），会退化到O（N）。
• 空间复杂度O（1）：low，high，mid 变量使用常数大小的额外空间。