Monday, March 9, 2015

153. Find Minimum in Rotated Sorted Array

Q:

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.


A:  

*************分别找两边最小的,然后取最小的。


public class Solution {
    public int findMin(int[] num) {
        return findMin(num,0,num.length-1);
    }
    private int findMin(int[] num, int left, int right){
        if(left==right || num[right]>num[left])
            return num[left];
        int mid = (left+right)/2;
        int l = findMin(num,left,mid-1);
        int r = findMin(num,mid+1,right);
        return Math.min(num[mid], Math.min(l,r));
    }
}

*****************上面的还是太慢,  看这个*********

public class Solution {
    public int findMin(int[] nums) {
        return helper(nums,0, nums.length-1);
    }
    private int helper(int[] nums, int start, int end){
        if(nums[start] <= nums[end])
            return nums[start];
        int mid = (start+end)/2;
        if(start==mid)
            return nums[end];
        return nums[start]<nums[mid]?helper(nums, mid+1, end) : helper(nums,start, mid);
    }
}
 




No comments:

Post a Comment