Question

Follow up for "Find Minimum in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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.

Solution

抓住数组的特点。

Code

class Solution {public:    int findMin(vector
    
     & nums) {        int size = nums.size();        if (size == 1)            return nums[0];        int low = 0;        int high = size - 1;        while (low < high) {            // 没用递归，所以注意求中间节点的方法            int mid = low + (high - low) / 2;            // 如果更小，那么会比右边的都小            if (nums[mid] < nums[high])                high = mid;            // 如果更大，那最小的肯定在右边            else if (nums[mid] > nums[high])                low = mid + 1;            // 如果相等，不知道最大值在左边还是在右边            else                high--;        }        return nums[low];    }};