首页 > 其他 > 详细

Find Minimum in Rotated Sorted Array II

时间:2014-10-29 18:42:19      阅读:229      评论:0      收藏:0      [点我收藏+]

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

原文:http://www.cnblogs.com/Kai-Xing/p/4059785.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!