题目描述

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

题目解读

• 剑指Offer 83

代码

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left  = 0;
        int right = rotateArray.size() - 1;
        int mid = left;

        if(rotateArray.size() == 0){
            return 0;
        }

        while(rotateArray[left] >= rotateArray[right]){
            if(right - left == 1){
                mid = right;
                break;
            }

            mid = (left + right) / 2;
            // 如果下标为 left right mid 指向的三个数字相等
            // 则只能顺序查找
            if(rotateArray[mid] == rotateArray[left] && rotateArray[mid] == rotateArray[right]){
                return MinInOrder(rotateArray, left, right);
            }

            if(rotateArray[mid] >= rotateArray[left]){
                left = mid;
            }else if(rotateArray[mid] <= rotateArray[right]){
                right = mid;
            }
        }
        return rotateArray[mid];
    }
    // 顺序查找
    int MinInOrder(vector<int>& rotateArray, int left, int right){
        int result = rotateArray[left];
        for(int i = left+1; i <= right; i++){
            if(result > rotateArray[i]){
                result = rotateArray[i];
            }
        }
        return result;
    }
};

int main(){
    Solution ss;
    int min;
    vector<int> aa;

    // 两套测试数据
    // aa.push_back(3);
    // aa.push_back(4);
    // aa.push_back(5);
    // aa.push_back(1);
    // aa.push_back(2);

    aa.push_back(1);
    aa.push_back(0);
    aa.push_back(1);
    aa.push_back(1);
    aa.push_back(1);

    min = ss.minNumberInRotateArray(aa);
    cout<<min<<endl;
}

总结展望

• 当以后遇到有序(部分有序)的数组时，要思考用二分查找的思想来解题，使效率最大化.
• 推荐看书上的解题思路，由浅入深，很好.
• 关于代码逻辑建议看书上的思路.