154. Find Minimum in Rotated Sorted Array II.md

154. Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

Solution

相比153还是有挺多坑要注意的，比如[3,3,3,1,3]，这种情况mid==st==ed，就没法直接把st或者ed移动到中间。所以最坏情况下复杂度变成了O(n)。

移动时候的条件判断要注意，写了很多次才通过的。

不过对于hard难度这题还是偏简单了。

Code

class Solution {
    public int findMin(int[] nums) {
        if(nums.length==1)
            return nums[0];
        
        int st = 0;
        int ed = nums.length-1;
        int mid = 0;
        while(st < ed-1)
        {
            mid = (st+ed)/2;
            if(nums[mid]==nums[ed] && nums[mid]==nums[st])
            {
                ed --;
                st ++;
            }
            else if(nums[mid]<=nums[ed])
                ed = mid;
            else if(nums[mid]>=nums[st])
                st = mid;
        }
        return Math.min(nums[st],nums[ed]);
    }
}