A recursive solution


  • 0
    H
    public class Solution {
         public static int find(int a[], int i, int j) {
            //for the base case i==j, len of a is 1
            if (i == j) return a[i];
    
            //for the duplication case, if a[i] is minimum, a[j] should be minimum also,so safe to remove one of them
            if (a[i] == a[j]) return find(a, i+1, j);
    
            // in this case, from a[i] to a[j] forms a non decreasing sequence, a[i] should be the min
            if (a[i] <  a[j]) return a[i];
    
            // the last case, if the array  consists of two non decreasing sequences, our task is to shrink the size
            // and eventually, at the end of the recursion, pick the first array element as min when the array is
            // a non-decreasing sequence
            int mid = (i + j) / 2;
            if (a[mid] >=  a[i]) {
                return find(a, mid + 1, j);
            } else {
                return find(a, i, mid);
            }
        }
        
        
        public static int findMin(int a[]) {
            return find(a, 0, a.length - 1);    
        }
    
    }
    

    the comments is self-explained the way I solve this problem. it's very very interesting to share one thing with you guys, this morning I was asked to write the solution for this problem in a interview, what a coincidence!
    but , also very interesting , I didn't have a idea this morning, since I just slept 3 hours last night.

    " So have a good sleep is the most important thing for a interview"

    :-)


  • 0
    T

    Agree, sleep plays a critical role in thinking and learning. sleeping zzzZ


Log in to reply
 

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