劍指offer11 旋轉數組的最小數字

    把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。

    輸入一個升序的數組的一個旋轉，輸出旋轉數組的最小元素。

    例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。

    數組可能包含重複項。

注意：數組内所含元素非負，若數組大小為0，請傳回-1。

樣例

輸入：nums=[2,2,2,0,1]
輸出：0
           

思路：

    首先判斷數組left位置上的數值是否小于right位置上的，若是，說明數組是一個遞增的數組，則直接傳回nums[left]上的數值。否則，開始進入循環：

    判斷數組中是否隻有兩個數值，若是，則直接結束并傳回right位置上的數值。

    判斷right、left、mid三個位置上的元素是否都重複，若都重複則搞不清最小值是在前半段還是後半段，隻能順序周遊數組，并直接傳回最小值。如：[1,0,1,1,1]和[1,1,1,0,1]

    right、left、mid上的三個值不相等時，若mid上的數值大于或者等于left，則最小值在後半段， 否則在前半段。

AcWing-22 C++ code：

class Solution {
    public:
        int findMin_n(vector<int>& nums, int left, int right){
            int min = nums[left];
            for(int i = left; i <= right; i++){
                if(min > nums[i]){
                    min = nums[i];
                }
            }
            return min;
        }
        
        int findMin(vector<int>& nums) {
            if(nums.size() == 0){
                return -1;
            }
            int n = nums.size();
            for(int i = 0; i < n; i++){
                if(nums[i] < 0){
                    return -1;
                }
            }
            
            int left = 0;
            int right = n - 1;
            int mid = left;
            
            while(nums[right] <= nums[left]){
                if(right - left == 1){
                    mid = right;
                    break;
                }
                
                mid = left + (right - left) / 2;
    
                if(nums[left] == nums[right] && nums[mid] == nums[left]){
                    return findMin_n(nums, left, right);
                }
                
                if(nums[mid] >= nums[left]){
                    left = mid;
                }else{
                    right = mid;
                }
                
            }
            return nums[mid];
            
        }
    };
           

牛客網 C++ code：

class Solution {
public:
    int minNumberInRotateArrayCore_n(vector<int> &nums){
        int res = nums[0];
        for(auto x : nums){
            if(x < res){
                res = x;
            }
        }
        return res;
    }
    int minNumberInRotateArrayCore_logn(vector<int> &nums){
        int left = 0;
        int right = nums.size() - 1;
        int mid = left + (right - left) / 2;
        while(nums[left] >= nums[right]){
            if(right - left <= 1){
                break;
            }
            mid = left + (right - left) / 2;
            if(nums[left] <= nums[mid]){
                left = mid;
            }else{
                right = mid;
            }
        }
        return nums[left] > nums[right] ? nums[right] : nums[left];
    }
    int minNumberInRotateArray(vector<int> nums) {
        if(nums.size() == 0){
            return 0;
        }else if(nums.size() == 1){
            return nums[0];
        }
        int left = 0;
        int right = nums.size() - 1;
        int mid = left + (right - left) / 2;
        if(nums[left] == nums[mid] && nums[left] == nums[right]){
            return minNumberInRotateArrayCore_n(nums);
        }else{
            return minNumberInRotateArrayCore_logn(nums);
        }
    }
};
           

AcWing-22 python code：

class Solution:
    def findMin_n(self, nums, left, right):
        min_num = nums[left]
        for i in range(left, right + 1):
            if min_num > nums[i]:
                min_num = nums[i]
        return min_num
        
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return -1
        
        n = len(nums)
        for i in range(n):
            if nums[i] < 0:
                return -1
        
        left = 0
        right = n - 1
        mid = left
        while nums[right] <= nums[left]:
            
            if right - left == 1:
                mid = right
                break
            
            mid = left + (right - left) // 2
            
            if nums[left] == nums[right] and nums[left] == nums[mid]:
                return self.findMin_n(nums, left, right)
            
            if nums[mid] >= nums[left]:
                left = mid
            else:
                right = mid
            
        return nums[mid]