Question: 

题目：

Follow up for "Find Minimum in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

 

思路：

两端寻找，跳过重复项，直至 nums[start] 与前项不同，nums[end] 与后项不同，且nums[start] 与 nums[end] 不相同。

其他部分，同 Find Minimum in Rotated Sorted Array。

 

1 public int findMin(int[] nums) { 2     if(nums == null || nums.length == 0) { 3         return 0; 4     } 5      6     int start = 0; 7     int end = nums.length - 1; 8     int minNum = nums[start]; 9     10     while(start < end) {11         int startNum = nums[start++];12         int endNum = nums[end--];13         minNum = Math.min(minNum, Math.min(startNum, endNum));14         15         while(start < end && nums[start] == startNum) {16             start++;17         }18         19         while(end > start && nums[end] == endNum) {20             end--;21         }22         23         if(start == end) {24             return Math.min(minNum, nums[start]);25         } else if(nums[start] == nums[end]) {26             continue;27         }28         29         int mid = (start + end)/2;　　　　// 此处 nums[mid],nums[start],nums[end]的值将均不同30         if(nums[start] < nums[end]) {31             return Math.min(minNum, nums[start]);32         } else if(nums[end] < nums[mid]) {33             start = mid + 1;34             minNum = Math.min(minNum, nums[end]);35         } else if(nums[start] > nums[mid]) {36             start++;37             end = mid;38             minNum = Math.min(minNum, nums[mid]);39         } 40     }41     42     return minNum;43 }