LeetCode - 154. Find Minimum in Rotated Sorted Array II

Question

题目

解析

• 递归解法和 LeetCode153 一样，只是要注意的是，如果 nums[R] == nums[L] 的时候，就不能判断是 Rotated Array ，而上一题也没有判断，所以是可以的；
• 只是非递归解法的时间复杂度和那个不同了，因为当某个区间 L、R 中出现 nums[L] == nums[L] 的时候就不能直接返回 nums[L] ，而需要继续递归，所以上面那个表格中的绿色部分都会消失，所以时间复杂度是 O(n) = 2 * T(n/2) = O(n) ；
• 非递归解法和上面那个有点不同，也就是在区间端点相同以及 nums[mid] 相同的情况下，做不同的处理，具体可看 剑指 Offer 中的题解。

class Solution {
    // have duplicate elements
    public int findMin(int[] nums) {
        if(nums == null || nums.length == 0)
            return -1;
        if(nums.length == 1 || nums[nums.length - 1] > nums[0])
            return nums[0];
    
        int L = 0, R = nums.length - 1;
        
        while(nums[L] >= nums[R]){   // ensure it is rotated, notice >= instead >, have duplicate elements
            if(L + 1 >= R)
            // if(L + 1 == R)   //is ok
                return nums[R];
            int mid = L + (R - L)/2;
            
            // this is the different with the The previous question
            if(nums[L] == nums[mid] && nums[mid] == nums[R]){ // can't judge
                for(int i = L+1; i <= R; i++){
                    if(nums[i] < nums[i-1])
                        return nums[i];
                }
            }
            // ok 
            // if(nums[mid] >= nums[L])  // notice >=
            //     L = mid;
            // else 
            //     R = mid;
            
            // below is ok
            if(nums[mid] >= nums[L])  // the min value is in the second half of the array
                L = mid+1;
            else 
                R = mid;
            
            //but below is error
            // if(nums[mid] >= nums[L]) 
            //     L = mid;
            // else 
            //     R = mid-1;
        }
        return nums[L];  // nums[L] < nums[R], directly return the nums[L]
    }
}