LeetCode 154. Find Minimum in Rotated Sorted Array II

Problem:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution:

At first I did not see the array may contain duplicates, which really bugged me.

public class Solution {
    int[] myNums;
    public int findMin(int[] nums) {
        myNums = nums;
        if (nums.length < 10) {
            // avoid trivial cases
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < min) min = nums[i];
            }
            return min;
        }
        return getMin(0, nums.length - 1);
    }
    
    private int getMin(int start, int end) {
        int mid = (start + end) / 2;
        int left = start + (end - start) / 4;
        int right = end - (end - start) / 4;
        if (start > myNums.length - 1) return myNums[myNums.length - 1];
        if (end < 0) return myNums[0];
        if (end - start < 1) return myNums[start];
        if (myNums[left] <= myNums[mid] && myNums[mid] <= myNums[right]) {
            int opt1 = getMin(start, left - 1);
            int opt2 = getMin(right + 1, end);
            return Math.min(opt1, opt2);
        }
        else if (myNums[left] > myNums[mid]) {
            return getMin(left+1, mid);
        }
        else if (myNums[mid] > myNums[right]) {
            return getMin(mid+1, right);
        }
        return 0;
    }
}

Comments are closed.