LeetCode 154. 尋找旋轉排序數組中的最小值 II（java代碼和思路分析)

題目傳送門

解題流程

• 解題思路：
• 代碼實作：
• 複雜度

解題思路：

和上一道題其實一樣，直接二分即可。

隻不過有些地方影響了二分的判斷。

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        if(nums[0] < nums[r]) return nums[0];
        while (l < r) {
            int mid = l + r >> 1;
            if(nums[mid] >= nums[0]) l = mid + 1;
            else r = mid;
        }
        return nums[r];
    }
}
           

這是上一題的代碼，觀察一下這兩個判斷。

之前隻要nums[mid]大于等于最左邊，我們一定可以判斷答案在mid右邊，因為不存在重複元素。

現在有了重複元素，就産生了nums[mid]大于等于最左邊，但答案卻不在mid右邊的情況。具體情況為：

假設最小值右側全部為nums[0]，那麼mid如果落在了這部分，那明明答案在mid左邊，但是按照上邊的邏輯卻向右側去尋找，這就産生了錯誤。

[3,4,6,1,2,3,3,3,3,3,3]

像這樣11個元素，mid第一次為5，nums[mid] = 3，如果此時向右明顯錯誤。

我們解決它也很簡單，将右側等于nums[0]的全部删掉。

這樣大于等于nums[0]就一定向右找，上面的代碼就對了。

代碼實作：

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while(l < r && nums[r] == nums[0]) r -- ;
        if(nums[0] < nums[r]) return nums[0];
        while (l < r) {
            int mid = l + r >> 1;
            if(nums[mid] >= nums[0]) l = mid + 1;
            else r = mid;
        }
        return nums[r];
    }
}
           

複雜度

時間複雜度最壞是O(n)，即把所有元素都删掉了，隻留下了最左面的那個。

奇怪，我為啥不直接掃描一遍求一個最小值。