題目

有一個長度為 n 的非降序數(shù)組，比如[1,2,3,4,5]，將它進(jìn)行旋轉(zhuǎn)，即把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，變成一個旋轉(zhuǎn)數(shù)組，比如變成了[3,4,5,1,2]，或者[4,5,1,2,3]這樣的。請問，給定這樣一個旋轉(zhuǎn)數(shù)組，求數(shù)組中的最小值。

數(shù)據(jù)范圍：1≤n≤10000，數(shù)組中任意元素的值: 0≤val≤10000

要求：空間復(fù)雜度：O(1) ，時間復(fù)雜度：O(logn)

示例1

輸入：
[3,4,5,1,2]
返回值：
1

示例2

輸入：
[3,100,200,3]
返回值：
3

思路

二分法：

• mid = (start + end) / 2 為二分的中間位置。
• mid，start,right分為三種情況：
  • nums[mid] > nums[end]時， 那么最小值一定在 [mid+1,end]區(qū)間中；
  • nums[mid] = nums[end]時，無法判斷最小值在哪個區(qū)間，所以此時只能縮小end的值；
  • nums[mid] < nums[end]時，那么最小值一定在[start,mid]區(qū)間內(nèi)。

解答代碼

class Solution {
public:
    /**
     * @param nums int整型vector 
     * @return int整型
     */
    int minNumberInRotateArray(vector<int>& nums) {
        // write code here
        int start = 0;
        int end = nums.size() - 1;
        while (start != end) {
            int mid = (start + end) / 2;
            if (nums[mid] > nums[end]) {
                //最小的數(shù)字在mid右邊
                start = mid + 1;
            } else if (nums[mid] == nums[end]) {
                //無法判斷，一個一個試
                end = end - 1;
            } else if (nums[mid] < nums[end]) {
                //最小數(shù)字要么是mid要么在mid左邊
                end = mid;
            }
        }
        return nums[end];
    }
};