An O(n) solution with short code and another solution using binary search


  • 0
    X
    public int findMin(int[] num) {
        for(int i = 0;i < num.length-1; i++)
        {
            if(num[i] > num[i+1])
                return num[i+1];
        }
        return num[0];
    }
    

    search for the first item that is smaller than its previous one, and that is the answer. If no item is found, it means the first item is the answer.

    public int findMin(int[] num) {
        
        return rf(0,num.length-1,num);
    }
    
    private int rf(int left, int right, int[] num)
    {
        if(right - left <= 1)
        {
            if(num[left] >= num[right])
                return num[right];
            else
                return num[left];
        }
        
        int mid = (left+right)/2;
        if(num[mid] == num[left] && num[mid] == num[right])
        {
            int a = rf(left,mid,num);
            int b = rf(mid,right,num);
            return a<b? a : b;
        }
        else if(num[mid] <= num[left] && num[mid] <= num[right])
            return rf(left,mid,num);
        else if(num[mid] >= num[left] && num[mid] <= num[right])
            return rf(left,mid,num);
        else //(num[mid] >= num[left] && num[mid] >= num[right])
            return rf(mid,right,num);
    }
    

    one point I think needs to explain: only in (num[mid] == num[left] && num[mid] == num[right]) condition, we don't know where the minimum stays, so calculate both and compare.
    if all items in the array are the same, time complexity is O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.