O(n) method in Java, a little bit complicated because I check for 4 situations


  • 0
    S

    I got this soln when I was doing Find Minimum in Roated Sorted Array, I think it should also works for II, and yes, it works!

    public int findMin(int[] num) {
        if(num==null){return 0;}
        if(num.length<2) {return num[0];}
        for(int i = 1; i < num.length; i++){
            if(isDescending(num[i-1], num[i])){
                continue; //continue if it is Des
            }
            else{ 
                if(num[i-1] < num[num.length-1]){
                    return num[i-1]; // avoid Asc then Des again
                
                }
                else{ continue;} //if Asc and Des again keep checking if Descending
                                           
            }
            
        }
        return num[num.length-1]; //if all are descending, the min is the last
    }
    
    public boolean isDescending(int prev, int cur){
        if(prev >= cur) {return true;}
        else{return false;}
    }

  • 0
    D

    if you want to do it in O(n) time, you can organize your code as below.
    However, there is a better solution than O(n). Keep looking for ot ^_^

    public class Solution {
        public int findMin(int[] num) {
            //
            int min = num[0];
            for(int i = 1; i < num.length; i++){
                if(num[i] >= num[i-1])
                    continue;
                if(num[i] < min)
                {
                    min = num[i];
                }
            }
            return min;
        }
    }

  • 0
    S

    Yep, I've figured out the logN method as well. Thanks for your answer.


  • 0
    W

    I think the author expect something better than O(n). Because if it's O(n) why I don't use a min variable and scan all the elements of the array?


Log in to reply
 

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