首页 > 代码库 > Find Minimum in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array II

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.

分析:此题的难点在于duplicate的处理,最坏情况(全部是相同数)时间复杂度是O(n)。此题在实现过程中,返回条件跟Find Minimum in Rotated Sorted Array I不同,优点是不会漏掉一些特殊情况且易于理解。代码如下:

class Solution {public:    int findMin(vector<int> &num) {        int n = num.size();        if(n == 1) return num[0];        if(n == 2) return min(num[0], num[1]);        if(num[0] < num[n-1]) return num[0];                int l = 0, r = n - 1;                while(l <= r){            if(l == r) return num[l];            if(l == r-1) return min(num[l], num[r]);            int mid = (l + r)/2;            if(num[mid] > num[0])                l = mid + 1;            else if(num[mid] < num[0])                r = mid;            else if(num[0] > num[n-1])                l = mid + 1;            else {//deal with duplicates                if(mid > n-1-mid){                    int tmp = mid;                    while(tmp < n-1 && num[tmp] == num[tmp+1])                        tmp++;                    if(tmp == n-1)                        r = mid;                    else l = tmp + 1;                }else {                    int tmp = mid;                    while(tmp > 0 && num[tmp-1] == num[tmp])                        tmp--;                    if(tmp == 0)                        l = mid;                    else r = tmp - 1;                }            }        }    }};

 

Find Minimum in Rotated Sorted Array II