4.21数组旋转找最小值 - WisperDin/blog GitHub Wiki

题目描述

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

思路

在数组旋转后，一个数组被划分成了两个有序部分，应利用好这个特性来解决问题

注意数组中可能会有重复的元素（非递减序列）

  1. 暴力遍历找最小元素，时间复杂度O(n)

  2. 稍微优化的遍历，从起始位置遍历，直至发现后一个元素比前一个元素要小，该元素就是最小元素，如一直没发现有这种情况，则取第一个元素。复杂度取决于旋转的元素个数

  3. 二分查找，同样先处理没旋转的情况，之后

    考虑到数组两部分都是有序的，假设旋转到后面的数组部分为A，剩下的部分为B，数组构成[B,A] B中任意一个元素>=A中任意一个元素

    • 若start<=mid [start,end] 则这部分必定为非递减的，区间内仅存在B的元素（B的元素不一定全存在在这个区间）所以 start > mid 时， A，B元素的交界处必定在此处
    • 若mid <= end [mid,end] 类似地，区间内仅存在A的元素，所以 mid > end 时 ，A，B 元素交界处必定在此处
    • 现在考虑除 (start >mid || mid >end) 的情况 即 (start <= mid <= end) ，此情况其实就是未旋转的情况，已经在一开始排除掉，而且在二分查找中每次的进入A，B交界处的区间，也不会出现这种情况
    • 最终情况： 注意当最后二分查找区间缩小至只有两个元素时，此时找到的就是A，B组的交界处，直接取end位置的元素返回即可

二分法实现代码

class Solution {
public:
    
    int minNumberInRotateArray(vector<int> rotateArray) {
        if (rotateArray.size()==0)
            return 0 ;
        int start = 0;
        int end = rotateArray.size()-1;
        int mid;
        //直接处理没有旋转的情况
        if (rotateArray[0]<rotateArray[end])
            return rotateArray[0];
        while (true){
            if (start+1==end)
                return rotateArray[start]>rotateArray[end]?rotateArray[end]:rotateArray[start];
            mid = (start+end)/2;
            //选 (前大于后) start>mid || mid > end 的部分继续二分
            if (rotateArray[start]>rotateArray[mid]){
                end = mid;
                continue;
            }
            if (rotateArray[mid] > rotateArray[end]){
                start = mid;
                continue;
            }
            //不可能出现的情况
            return rotateArray[end];
        }        
    }
};

优化的遍历方法实现代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0)
            return 0;
        int firstEle = rotateArray[0];
        int i,cursor;
        for (i = 1,cursor = 0 ; i<rotateArray.size();i++,cursor++){
            if(rotateArray[i]<rotateArray[cursor])
                break;
        }
        return i==rotateArray.size()?firstEle:rotateArray[i];
    }
};
⚠️ **GitHub.com Fallback** ⚠️