06: 旋转数组的最小数字

题目描述

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

解题思路

• 第一次写的时候直接就顺序遍历了（S1), 也是A了的，所以可见企业的oj,其实对复杂度要求还是很松的，样例应该不强。
• 第二次就是先二分找到了旋转点， 在二分查找目标，这个写是leetcode 33 写的（S2)。

AC代码

• S1

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(!rotateArray.size())
            return 0;
        
        int min = INT_MAX;
        
        for(auto& e:rotateArray){
            if(e < min)
                min = e;
        }
        
        return min;
    }
};

• S2

class Solution {
public:
    int search(vector<int>& nums, int target){
        
        if(nums.empty())
            return -1;
        
        if(nums.size() == 1)
            return target == nums[0] ? 0 : -1;
        
        int rotate_index = search_rotate_index(nums);

        int l = rotate_index + 1, h = nums.size() - 1;
        if(target >= nums[0] && target <= nums[rotate_index])
        {
            h = l;
            l = 0;
        }

        while(l <= h)
        {
            int m = (l + h)/2;
            if(nums[m] > target)
                h = m - 1;
            else if(nums[m] < target)
                l = m + 1;
            else
                return m;            
        }

        return -1;
    }

    int search_rotate_index(vector<int>&nums)
    {
        int l = 0, h = nums.size() - 1;
        
        if(nums[l] < nums[h])
            return 0;
        
        while(l <= h)
        {
            int m = (l +  h) / 2;
            if(nums[m] > nums[m + 1])
                return m;
            else
            {
                if(nums[m] >= nums[l])
                    l = m + 1;
                else
                    h = m - 1;
            }
        }
        return 0;
    }
};