Sunday, January 11, 2015

LeetCode 154: 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 n = num.length;
        
        if (n == 0)
            return 0;
            
        if (n == 1)
            return num[0];
            
        for (int i = 0; i < n-1; i++)
            if (num[i] > num[i+1])
                return num[i+1];
        
        return num[0];
    }
}

No comments:

Post a Comment