2015年3月21日星期六

Find Minimum in Rotated Sorted Array II

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.

public class Solution {
    public int findMin(int[] num) {
        int s = 0;
        int e = num.length-1;
        if(num[s]<num[e]) return num[s];
       
        while(s<e && num[s]==num[s+1]) s++;
        while(s<e && num[e]==num[e-1]) e--;
        while(s<=e) {
            int m = (s+e)/2;
            if(m!=0 && num[m]<num[m-1]) {
                return num[m];
            }
            if(num[s]==num[e]) {
                s++;
            } else if(num[s]<num[e]) {
                return num[s];
            } else {
                if(num[m]>=num[s]) {
                    s = m+1;
                } else {
                    e = m-1;
                }
            }
        }
        return num[0];
    }
}


public class Solution {
    public int findMin(int[] num) {
        int s = 0;
        int e = num.length-1;
        if(num[s]<num[e]) return num[s];
       
        while(s<=e) {
            int m = (s+e)/2;
            if(m!=0 && num[m]<num[m-1]) {
                return num[m];
            }
            if(num[s]<num[e]) {
                return num[s];
            }
            if(num[s]==num[e]) {
                if(num[s]>num[0]) s++;
                else e--;
            } else {
                if(num[m]>=num[s]) {
                    s = m+1;
                } else {
                    e = m-1;
                }
            }
        }
        return num[0];
    }
}

===============

public class Solution {
    public int findMin(int[] num) {
        int lo = 0;
        int hi = num.length - 1;
        int mid = 0;

        while(lo <= hi) {
            mid = lo + (hi - lo) / 2;

            if (num[mid] < num[hi]) {
                hi = mid;
            }
            else if (num[mid] > num[hi]) {
                lo = mid + 1;
            }
            else { // when num[mid] and num[hi] are same
                hi--;
            }
        }
        return num[lo];
    }
}

没有评论:

发表评论