153/154. Find Minimum in Rotated Sorted Array I/II

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.
思路: 153中不包括duplicate. 直接二分,target选最右边元素。 每次mid跟target进行比较,如果大于target,说明mid在左边逆序,最小值在右边,start=mid; 如果小于target,说明mid在右边,往左边找,end = mid; 最后再返回start跟end中较小的元素。

复杂度: time O(logn), space O(1)

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        int target = nums[end];
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] <= nums[end]) {
            return nums[start];
        }
        return nums[end];
    }
}

154 存在duplicates的情况。
思路: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;
复杂度: time O(n), space O(1)

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[end] < nums[mid]) {
                start = mid;
            } else if (nums[end] > nums[mid]) {
                end = mid;
            } else { 
                end--;
            }
        }
        return Math.min(nums[start], nums[end]);

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s