题目:
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.
思路:
本题思路跟“没有重复元素”的情况相似。当没有重复元素的时候,首先判断首元素和末元素大小关系。如果首元素小于末尾元素,则不用分析,一定是顺序排列的,返回第一个就是最小的。否则,寻找中间位置的值,若中间位置值大于第首元素,则最小值一定在右边的一半数组中;否则在左边一半的数组中。
当有重复元素时,在比较首元素和末元素的时候先要去重保证两元素不等,并对坐标关系进行判断(如果首末的位置最终到了同一个位置,则整个数组都是同一个值)这样才能知道排列趋势。
在非顺序排列的情况下,进行比较:如果mid和start的元素一样,则start++直到变成该值的最后一个的位置。
如果mid和end一样,则end--直到变成该值的第一个值;不用考虑start位置上的值==end位置上的值的情况。
注意:
如何知道最终结果是哪个?在while循环中的条件应该是只剩两个元素,也就是start<end-1,这时,当start=end-1的时候就会停止,最小值一定在这两个中(二分法锁定的最终结果)。
AC代码:
public int findMin(int[] num) { if (num == null) return 0; if (num.length == 1) return num[0]; int i = 0; for (i = num.length - 1; i >= 0 && num[i] == num[0]; i--) ; if (i == -1) return num[0]; int start = 0, end = i, mid = 0; if (num[start] < num[end]) { return num[start]; } else { while (start < end-1) { mid = (start + end) >> 1; if (num[start] == num[mid]) { for (start = mid + 1; start < end && num[start] == num[mid]; start++) ; start--; } else if (num[end] == num[mid]) { for (end = mid - 1; end > start && num[end] == num[mid]; end--) ; end++; } else { if (num[mid] < num[start]) end = mid; else start = mid; } } } return num[end]>num[start]?num[start]:num[end]; }