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