O(n) Java solution with 5 line code


  • 0
    K

    But can anyone share me a O(logn) or more elegant solution?

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

    }


  • 0
    T

    Try this..

    public int searchMinDupRotatedArray(int[] array, int start ,int end){
        if(start == end) return array[start];
        
        if(start + 1 == end){
            return array[start] <= array[end] ? array[start] : array[end];
        }
        
        int mid = (start+end)/2; 
        if(array[mid] < array[end])
            return searchMinDupRotatedArray(array, start, mid);
        else if(array[mid] > array[end])
            return searchMinDupRotatedArray(array, mid+1, end);
        else{
            if(array[start]!= array[mid])
                return searchMinDupRotatedArray(array, start, mid);
            
            int right = searchMinDupRotatedArray(array, mid+1, end);
            int left = searchMinDupRotatedArray(array, start, mid-1);
            return left <= right ? left : right;
        }   
    }

  • 0
    G

    This is not a O(log n ) solution, and in fact the best you can do is a linear solution. Imagine you have an array filled with 1's and one 0. If you are not lucky to read the 0 quickly, you have to look at all elements of the array to distinguish this array from one in which all elements are 1.


  • 0
    Q

    I prefer this one. Though i know the question is asking for binary search.


Log in to reply
 

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