LeetCode 153. 尋找旋轉排序陣列中的最小值【c++/java詳細題解】

1、題目

已知一個長度為 n 的陣列，預先按照升序排列，經由 1 到 n 次 旋轉 后，得到輸入陣列，例如，原陣列 nums = [0,1,2,4,5,6,7] 在變化后可能得到：

• 若旋轉 4 次，則可以得到 [4,5,6,7,0,1,2]
• 若旋轉 7 次，則可以得到 [0,1,2,4,5,6,7]

注意，陣列 [a[0], a[1], a[2], ..., a[n-1]] 旋轉一次 的結果為陣列 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] ，

給你一個元素值 互不相同 的陣列 nums ，它原來是一個升序排列的陣列，并按上述情形進行了多次旋轉，請你找出并回傳陣列中的 **最小元素 **，

示例 1：

輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原陣列為 [1,2,3,4,5] ，旋轉 3 次得到輸入陣列，

示例 2：

輸入：nums = [4,5,6,7,0,1,2]
輸出：0
解釋：原陣列為 [0,1,2,4,5,6,7] ，旋轉 4 次得到輸入陣列，

示例 3：

輸入：nums = [11,13,15,17]
輸出：11
解釋：原陣列為 [11,13,15,17] ，旋轉 4 次得到輸入陣列，

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整數 互不相同
• nums 原來是一個升序排序的陣列，并進行了 1 至 n 次旋轉

2、思路

(二分) O ( l o g n ) O(logn) O(logn)

為了便于分析，我們先將陣列中的數畫在二維坐標系中，橫坐標表示陣列下標，縱坐標表示陣列數值，如下所示：

我們發現：豎直虛線左邊的數滿足 n u m s [ i ] ≥ n u m s [ 0 ] nums[i]≥nums[0] nums[i]≥nums[0]，而豎直虛線右邊的數滿足 n u m s [ i ] < n u m s [ 0 ] nums[i]< nums[0] nums[i]<nums[0]，分界點就是整個陣列的最小值，陣列具有二分性，所以我們可以二分出最小值的位置，

程序如下：

• 1、在[l,r]區間中，l = 0, r = nums.size() - 1，我們去二分<num[0]的最左邊界，
• 2、當nums[mid] < nums[0]時，往左邊區域找，r = mid，，

• 3、當nums[mid] >= nums[0]時，往右邊區域找，l = mid + 1，

• 4、當只剩下一個數時，就是最小值的位置，

細節：

• 當陣列完全單調時，第一個數nums[0]最小，我們直接回傳即可，

時間復雜度分析： 二分查找，所以時間復雜度是 O ( l o g n ) O(logn) O(logn)，

3、c++代碼

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        if(nums[r] > nums[l]) return nums[0];  //升序陣列，陣列完全單調，第一個數最小
        while(l < r)
        {
            int mid = (l + r)/2;
            if(nums[mid] < nums[0])  r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

4、java代碼

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        if(nums[r] > nums[l]) return nums[0];  //升序陣列，陣列完全單調，第一個數最小
        while(l < r)
        {
            int mid = (l + r)/2;
            if(nums[mid] < nums[0])  r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
}

原題鏈接： 153. 尋找旋轉排序陣列中的最小值