LeetCode 153 Find Minimum in Rotated Sorted Array I
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.
You may assume no duplicate exists in the array.
對(duì)于sorted array直接考慮binary search谁尸。要分清楚情況浓镜，rotated sorted array存在一個(gè)很好的性質(zhì)泽腮，就是：
不管pivot在哪里蟀苛，開(kāi)頭的k個(gè)number，總是已經(jīng)排好序的７谈Ｍ笕谩！
如：
[0,1,2,3,4,5,6,7]
[6,7,0,1,2,3,4,5]
[2,3,4,5,6,7,0,1]
可以看到對(duì)于rotated sorted array择葡，只可能存在3種case！Ｈ病刁岸！
1）nums[left] < nums[mid] && nums[mid] < nums[right]
2）nums[left] > nums[mid] && nums[mid] < nums[right]
3）nums[left] < nums[mid] && nums[mid] > nums[right]
而對(duì)于一般的array脏里，還應(yīng)該存在：
4）nums[left] > nums[mid] && nums[mid] > nums[right]
即完全的逆序（對(duì)于任何一個(gè)substring她我，都不可能滿(mǎn)足）：
[7,6,5,4,3,2,1,0]
因此判斷的時(shí)候，也不用考慮這種情況迫横，只需要考慮：
nums[mid]與nums[right]的關(guān)系即可７摺！矾踱！
這里要注意恨狈，與常規(guī)binarySearch找某一個(gè)元素不同，
當(dāng)搜索左側(cè)區(qū)間時(shí)呛讲，mid=right禾怠，而不是mid=right-1；
這是因?yàn)榭紤]到mid到達(dá)邊界的時(shí)候１锤椤Ｂ鹗稀！
===================================
代碼：
public class Solution {
public int findMin(int[] nums) {
// Find the pivot and the number after the pivot is the minimum number?!
int n = nums.length;
int l = 0, r = n-1, mid = 0;
while (l < r) {
mid = l + (r-l) / 2;
if (nums[mid] > nums[r])
l = mid + 1;
else
r = mid;
}
return nums[l];
}
}
LeetCode 154 Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
若數(shù)組中存在duplicate雷逆，那么相比與上述的三種情況弦讽，又會(huì)出現(xiàn)一種：
[0,1,2,3,4,5,6,7]
[6,7,0,1,2,3,4,5]
[2,3,4,5,6,7,0,1]
[6,6,7,0,1,2,3,4,5,6,6] //即使存在duplicate，還是可以通過(guò)mid與兩側(cè)關(guān)系判斷
[2,2,3,4,5,6,7,0,1,2,2] //即使存在duplicate膀哲，還是可以通過(guò)mid與兩側(cè)關(guān)系判斷
[3,3,3,3,3,0,1,2,3] // 無(wú)法判斷在哪側(cè)
[3,0,1,2,3,3,3,3,3] // 無(wú)法判斷在哪側(cè)
即：
5）nums[mid]與nums[left]與nums[right]三者相同往产，因此無(wú)法確定到底pivot在左半側(cè)還是右半側(cè)。
解決方法
思路一：在判斷nums[mid]與nums[right]前
1 先判斷是否nums[mid]與nums[left]與nums[right]三者相同
2 若是某宪，則再判斷nums[mid-1]是否與nums[mid]相同
3 若是仿村，則左半部分全都相同，pivot在右側(cè)兴喂；反之蔼囊，則pivot在左側(cè)
4 若三者不同，則按照不存在duplicate的方法繼續(xù)判斷pivot位置
思路二：
比較trickyＵ跋搿Ｑ拐妗！
若三者相同蘑险，則將upper bound縮小滴肿，再確定縮小后的區(qū)間即可。
[3,3,3,3,3,0,1,2,3] // 無(wú)法判斷在哪側(cè)
[3,0,1,2,3,3,3,3,3] // 無(wú)法判斷在哪側(cè)
對(duì)于以上兩種情況佃迄，由于nums[mid]=nums[right]泼差，因此right--贵少，重新判斷縮小后的區(qū)間，此時(shí)變?yōu)椋?br>
[3,3,3,3,3,0,1,2]
[3,0,1,2,3,3,3,3]
發(fā)現(xiàn)第一與第二種case堆缘，均可以判斷出pivotＬ显睢！吼肥！
代碼：
public class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n-1, mid = 0;
while (l < r) {
mid = l + (r-l)/2;
if (nums[mid] > nums[r])
l = mid+1;
else if (nums[mid] < nums[r])
r = mid;
else
r--;
}
return nums[l];
}
}
