« Back
in Leetcode Java Array Binary Search read.

Leetcode 153 Find Minimum in Rotated Sorted Array.

This problem is really weird, cause you can use a very simple way to figure it out. The runtime difference is very little.

Problem 153 Find Minimum in Rotated Sorted Array

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.

You may assume no duplicate exists in the array.

My answer:

public class Solution {
    public int findMin(int[] nums) {
        Arrays.sort(nums);
        return nums[0];
    }
}

Looks like it gonna run out of time? Nope.

Runtime

So looks like it is working.

But I still want to find a normal way for this problem.

And I find divide and conquer.

public class Solution {
public int findMin(int[] num) {
    return findMin(num, 0, num.length - 1);
}

public int findMin(int[] num, int left, int right) {
    if (left == right)
        return num[left];
    if ((right - left) == 1)
        return Math.min(num[left], num[right]);

    int middle = left + (right - left) / 2;

    // not rotated
    if (num[left] < num[right]) {
        return num[left];

    // go right side
    } else if (num[middle] > num[left]) {
        return findMin(num, middle, right);

    // go left side
    } else {
        return findMin(num, left, middle);
    }
}
}
comments powered by Disqus