描述
假設(shè)一個旋轉(zhuǎn)排序的數(shù)組其起始位置是未知的（比如0 1 2 4 5 6 7 可能變成是4 5 6 7 0 1 2）你需要找到其中最小的元素蘸朋。數(shù)組中可能存在重復(fù)的元素。
注意事項
The array may contain duplicates.
樣例
給出[4,4,5,6,7,0,1,2] 返回 0
牢記
要考慮最小情況可能被越過
代碼
方法1：
public class Solution {
public int findMin(int[] num) {
// 這道題目在面試中不會讓寫完整的程序
// 只需要知道最壞情況下 [1,1,1....,1] 里有一個0
// 這種情況使得時間復(fù)雜度必須是 O(n)
// 因此寫一個for循環(huán)就好了砚婆。
// 如果你覺得智哀，不是每個情況都是最壞情況，你想用二分法解決不是最壞情況的情況捐晶，那你就寫一個二分吧冯键。
// 反正面試考的不是你在這個題上會不會用二分法惹盼。這個題的考點是你想不想得到最壞情況。
int min = num[0];
for (int i = 1; i < num.length; i++) {
if (num[i] < min)
min = num[i];
}
return min;
}
}
方法2：
public class Solution {
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == nums[end]) {
// if mid equals to end, that means it's fine to remove end
// the smallest element won't be removed
end--;
} else if (nums[mid] < nums[end]) {
end = mid;
// of course you can merge == & <
} else {
start = mid;
// or start = mid + 1
}
}
if (nums[start] <= nums[end]) {
return nums[start];
}
return nums[end];
}
}
總結(jié)：
方法2和不帶有重復(fù)元素的旋轉(zhuǎn)排序數(shù)組解法的區(qū)別就在于要考慮特殊情況惫确， 即一群重復(fù)元素中帶有一個更小的的元素手报，比如[1,1,-1,1],這種如果直接mid判斷會直接越過最小值
