Follow up for "Find Minimum in Rotated Sorted Array":Suppose a sorted array is rotated at some pivot unknown to you beforehand.
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
(i.e.,
0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).Find the minimum element.
The array may contain duplicates.
public class Solution { public int findMin(int[] num) { int n = num.length; if (n == 0) return 0; if (n == 1) return num[0]; for (int i = 0; i < n-1; i++) if (num[i] > num[i+1]) return num[i+1]; return num[0]; } }
No comments:
Post a Comment