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.

對于sorted array直接考慮binary search。要分清楚情況，rotated sorted array存在一個很好的性質(zhì)，就是：

不管pivot在哪里，開頭的k個number，總是已經(jīng)排好序的?。。?br> 如：
[0,1,2,3,4,5,6,7]
[6,7,0,1,2,3,4,5]
[2,3,4,5,6,7,0,1]

可以看到對于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]

而對于一般的array，還應(yīng)該存在：
4）nums[left] > nums[mid] && nums[mid] > nums[right]
即完全的逆序（對于任何一個substring，都不可能滿足）：
[7,6,5,4,3,2,1,0]

因此判斷的時候，也不用考慮這種情況，只需要考慮：
nums[mid]與nums[right]的關(guān)系即可?。?！

這里要注意，與常規(guī)binarySearch找某一個元素不同，
當(dāng)搜索左側(cè)區(qū)間時，mid=right，而不是mid=right-1；
這是因?yàn)榭紤]到mid到達(dá)邊界的時候！！！
===================================

代碼：

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，那么相比與上述的三種情況，又會出現(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，還是可以通過mid與兩側(cè)關(guān)系判斷
[2,2,3,4,5,6,7,0,1,2,2] //即使存在duplicate，還是可以通過mid與兩側(cè)關(guān)系判斷
[3,3,3,3,3,0,1,2,3] // 無法判斷在哪側(cè)
[3,0,1,2,3,3,3,3,3] // 無法判斷在哪側(cè)

即：
5）nums[mid]與nums[left]與nums[right]三者相同，因此無法確定到底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] // 無法判斷在哪側(cè)
[3,0,1,2,3,3,3,3,3] // 無法判斷在哪側(cè)

對于以上兩種情況，由于nums[mid]=nums[right]，因此right--，重新判斷縮小后的區(qū)間，此時變?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];
    }
}