旋转数组的最小数字

旋转数组的最小数字

三月 19, 2019

题目描述


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


    要做这道题，首先要讲一下非减排序数组是什么意思。起初以为只要不是减排序就可以，比如说{1,3,2,5,4}。但实际上并不是这样，找了很多资料都没有详细描述。（这里就要吐槽一下国内的某sdn和辣鸡某度，随便搜一下，全是千篇一律的文章，连标点符号都一字不差。有时候都怀疑，这些人就那么喜欢吃人家嘴里吐出来的东西么。）最后终于凭着自己的猜测和模糊的资料，得知原来非减序数组就是每个元素都大于等于后一个元素。例如，{1,2,3,4,5}，{0,1,1,1,1,1}等。

    主要思路：二分查找

  • 可以把旋转数组看作是前后两个非减排序的子数组
  • 用两个指针分别指向数组的第一个元素和最后一个元素
  • 求mid=(low + high) / 2
  • 如果mid位于后边数组的话，mid应该小于high，那么最小值应该在mid及自身之前，所以把high提到mid
  • 如果mid位于前边数组的话，mid应该大于low，那么最小值应该在mid及自身之后，所以把low后移到mid
  • 依次循环找到最小值
  • 但是上边讲非减排序数组也可以是{0,1,1,1,1,1}，那么它的旋转数组{1,1,1,1,0,1}的low、mid和high是相等的，就出现了问题，此时不知道最小值是再前边数组还是后边数组，所以就只能使用顺序查找来找出最小值了
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        //可以把旋转数组看作是前后两个非减排序的子数组
        if(rotateArray.size() == 0){
            cout << "rotateArray size is 0" << endl;
            return 0;
        }
        
        int mid = 0;
        int low = 0;
        int high = rotateArray.size() - 1;
        if(rotateArray[low] < rotateArray[high]){
            cout << "rotateArray is not rotated" << endl;
        }
        while(rotateArray[low] >= rotateArray[high]){
            
            if(high - low == 1){
                mid = high;
                break;
            }
            
            mid = (low + high) / 2;
            if(rotateArray[mid] == rotateArray[high] 
               && rotateArray[mid] == rotateArray[low]){
                //这里无法确定到底是应该取左边子数组 还是取右边子数组 
                //那么就交给顺序查找来做吧
                return minOrder(rotateArray, low, high);
            }else if(rotateArray[mid] <= rotateArray[high]){
                //如果mid位于后边数组的话 mid应该小于high
                //最小值应该在mid及之前 因为mid后边的值一定不小于自身的
                //那么把high提前到mid位置
                high = mid;
            }else if(rotateArray[mid] >= rotateArray[low]){
                //如果mid位于前边数组的话 mid应该大于low
                //最小值应该在mid及之后
                //所以把low后移到mid位置
                low = mid;
            }
            
            
        }
        
        return rotateArray[mid];
        
    }
    int minOrder(vector<int> &num, int low, int high){
        int min = num[low];
        for(int i = low + 1; i < high; i++){
            if(min > num[i]){
                min = num[i];
            }
        }
        
        return min;
    }
};
  1. 1. 题目描述