Leetcode 154 Find Minimum in Rotated Sorted Array II

triplebee

发布于 2018-01-12 14:51:18

4420

发布于 2018-01-12 14:51:18

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 a sorted array 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.

153的改进版，可能会有重复的数字出现，

所以需要单独讨论等于的情况，等于时上界下移，

这样在数字全部相同时会退化为O（n）复杂度

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-12-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除

duplicates