Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
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.
The array may contain duplicates.
思路1：採用排序（jdk中的快排），时间复杂度为O(nlogn)。代码例如以下 public class Solution { public int findMin(int[] num) { Arrays.sort(num); return num[0]; } } 思路2：採用一次性遍历。 时间复杂度为O(n)。代码例如以下 public class Solution { public int findMin(int[] num) { int min=Integer.MAX_VALUE; for(int i=0;i<num.length;i++){ if(min>num[i]) min=num[i]; } return min; } } 思路3：採用折半查找， 时间复杂度为O(logn)，代码例如以下 public class Solution { public int findMin(int[] num) { return minFind(num, 0, num.length - 1); } private int minFind(int[] num, int begin, int end) { int middle = (begin + end) / 2; if (begin == end) { return num[begin]; } else if (end == begin + 1) { return Math.min(num[begin], num[end]); } else if (end == begin + 2) { return Math.min(Math.min(num[begin], num[begin + 1]), num[end]); } if (num[begin] == num[end]) { return Math.min(minFind(num, begin, middle),minFind(num, middle, end)); } if (num[middle] < num[begin] && num[middle] <= num[end]) { return minFind(num, begin, middle); } else if (num[begin] <= num[middle] && num[end] < num[middle]) { return minFind(num, middle, end); } else if (num[begin] < num[middle] && num[middle] <= num[end]) { return minFind(num, begin, middle); }else if (num[begin] <= num[middle] && num[middle] < num[end]) { return minFind(num, begin, middle); } return 0; } }版权声明：本文博客原创文章，博客，未经同意，不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4721602.html
