Very clear Java Solution using Binary Search (1ms)


  • 1

    I believe my code can be more straight-forward without any confusing tricky code.
    It is augmented from the non-duplicate version. As we can see, the avg case is O(logn), but worst case O(n), in which case all the elements are duplicates!

    public class Solution {
        
        public int helper(int[] nums, int start, int end) {
            if(start==end)
                return nums[start];
            int mid  = start + (end - start) / 2;
            if(nums[mid] > nums[end])
                return helper(nums, mid+1 ,end);
            else if(nums[mid] < nums[end])
                return helper(nums, start, mid);
            else {
                if(nums[mid] == nums[start]) // we don't know the smallest is in right or left
                    return helper(nums, start+1, end);
                else // this case, we can confirm that the right of mid are all duplicates!
                    return helper(nums, start, mid);
            }
        }
        
        public int findMin(int[] nums) {
            return helper(nums, 0, nums.length-1);
        }
    }

Log in to reply
 

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