Short and Simple log(n) Solution


  • -1
       public static int findMin(int[] num) {
    		return findMin(num, 0, num.length-1);
    	}
    	public static int findMin(int[] num, int start, int end) {
    		if(end-start<=1) return Math.min(num[start],num[end]);
    		int middle = (start+end)/2;
    		if(num[start]<num[middle]) return (num[middle]<=num[end]) ? num[start] : findMin(num,middle,end);
    		else if(num[start]==num[middle]) return (num[middle]==num[end]) ? Math.min(findMin(num,start,middle), findMin(num,middle,end)) :findMin(num,middle,end);
    		else return (num[middle]<=num[end]) ? findMin(num,start,middle) : -1;
    	}
    

    The minimum will be at the rotation point.

    We need to take into account at each step num[start], num[middle], num[end] to find the rotation point, if it exist. The array can have just one point breaking the increasing trend.

    Let consider all the possible 9 cases:

    1. num[start] < num[middle] < num[end] => min=num[start]
    2. num[start] < num[middle] = num[end] => min=num[start]
    3. num[start] < num[middle] > num[end] => min between middle and end
    4. num[start] = num[middle] < num[end] => min between middle and end
    5. num[start] = num[middle] = num[end] => min could be everywhere, search recursively left and right and return the min between the two searches
    6. num[start] = num[middle] > num[end] => min between middle and end
    7. num[start] > num[middle] < num[end] => min between start and middle
    8. num[start] > num[middle] = num[end] => min between start and middle
    9. num[start] > num[middle] > num[end] => IMPOSSIBLE (array should have at least 2 rotation points)

  • 1
    C

    if these numbers are all the same, i think your algorithm will be O(n).


  • 1
    G

    You cannot distinguish an array of 1's from an array of 1's and one 0 unless you read all the elements of the array. This is true since the 0 could be placed anywhere and the array will still be sorted. Therefore, the best you can do is O(n) which is trivial. This is a trick question.


Log in to reply
 

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