LeetCode 0154 - Find Minimum in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array II

Desicription

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:

代码语言：javascript复制

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

Example 2:

代码语言：javascript复制

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

代码语言：javascript复制

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while(left < right) {
            int mid = (left   right) >> 1;
            if(nums[mid] > nums[right])
                left = mid   1;
            else if(nums[mid] < nums[right])
                right = mid;
            else {
                if(nums[left] == nums[mid])
                    left  , right--;
                else
                    right = mid;
            }
        }
        return nums[right];
    }
};

duplicates element find minimum this

1 人点赞