My java solution using recursion worst O(n) time when all number equals or O(lg n) otherwise


  • 0
    Z

    The solution just like Find Minimum in Rotated Sorted Array, using binary search, so it's O(lg n).

    The special case is when number of start equals number of middle, so instead of discarding one half of array, we only discard one number.

    The worst case is all the number in array are equals, it will degrade to O(n).

    public class Solution {
    
        public int findMin(int[] num) {
            return _findMin(num, 0, num.length - 1);
        }
    
        private int _findMin(int[] num, int start, int end) {
            if (num[start] < num[end]) {
                return num[start];
            }
    
            if (start == end) {
                return num[end];
            }
    
            if (start + 1 == end) {
                return num[end];
            }
    
            int mid = (end + start) / 2;
            if (num[mid] < num[start]) {
                return _findMin(num, start, mid);
            } else if (num[mid] > num[start]) {
                return _findMin(num, mid, end);
            } else {
                return _findMin(num, start + 1, end);
            }
        }
    }

  • 0
    S

    The runtime is not applicable.


  • 0
    L

    how about the case when 90% of the numbers are the same?


Log in to reply
 

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