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.
Note: binary search
Run time complexity is O(logn), space complexity is constant space
Run time complexity is O(logn), space complexity is constant space
public class Solution { public int findMin(int[] num) { if(num == null || num.length == 0) return 0; int l = 0, r = num.length - 1; while(l < r) { int mid = (l + r) / 2; if(num[mid] > num[r]) { l = mid + 1; }else { r = mid; } } return num[l]; } }
Or:
public class Solution { public int findMin(int[] num) { if(num == null || num.length == 0) return 0; int start = 0; int end = num.length - 1; int result = num[0]; while(start < end - 1) { int mid = (end + start) / 2; if(num[mid] > num[start]) { result = Math.min(num[start], result); start = mid + 1; }else if(num[mid] < num[start]) { result = Math.min(num[mid], result); end = mid - 1; }else { start++; } } result = Math.min(num[start], result); result = Math.min(num[end], result); return result; } }
No comments:
Post a Comment