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