[LeetCode]Find Minimum in Rotated Sorted Array，解題報告

[LeetCode]Find Minimum in Rotated Sorted Array，解題報告

前言

今天來杭州參加百阿培訓，住在4星級的旅館，加上快一月底了我都沒有幾篇博客產出，所以准備開始水LeetCode題目了，這裡介紹一個二分查找的應用。

題目

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.

思路

O(n)

看到這道題目，我的第一感覺是二分法，但是如何進行二分，卻沒有明確的思路出現在我的腦海中（悲劇，最近Android系統搞多了，算法能力急劇下降）。但是，如果這是面試的一道題目，你不可能因為你不會二分就放棄了這道題目的解答，因此我嘗試通過增加一點時間復雜度來解決這到題目，思路如下： 首先，定義一個boolean值的標志位flag，初始為false，循環遍歷找到了最小元素就置為true。定義數組num循環的起點begin為0，終點end為num.length - 1，循環的條件是begin < end。循環體內部，我們考慮，如果num[begin] > num[end]，說明了數組發生了旋轉，這時我們只需要將begin+1，繼續比較，直到找到第一個小於end的值即為最小值。如果num[begin] < num[end]，說明數組沒有發生循環，那最小值自然為num[begin]。 有了思路，代碼自然產出，AC代碼如下所示：

public class FindMinimumInRotatedSortedArray {
    public int findMin(int[] num) {
        if (num.length == 1) {
        	return num[0];
        }
        
        int begin = 0, end = num.length - 1;
        boolean flag = false;
        
        while (begin < end) {
        	if (num[begin] > num[end]) {
        		begin += 1;
        	} else {
        		flag = true;
        		break;
        	}
        }
        
        if (flag) {
        	return num[begin];
        } else {
        	return num[end];
        }
    }
}

雖然代碼AC了，但是對於一個追求效率的人來說，這種代碼顯然是不滿足要求的，因為該代碼的時間負責度為O(n)。如果采用二分查找算法，則時間復雜度為O(logn)，所以我們必須考慮對代碼的優化。

O(logn)

這個負責度我們必然要考慮二分算法了。百阿期間和一個小伙伴睡前討論得出了該解決方案。假設數組名為num，當我們確認了起點begin，終點end後，那麼mid所代表值的大小只有兩種可能： num[begin] < num[mid]。在一個被旋轉的數組中，當num[begin] < num[mid]時，那最小值min可能為num[begin]或者位於區間[mid + 1, end] 之間。num[mid] < num[end]。這種情況下，最小值min可能為num[mid]或者為區間[begin, mid - 1]中的值。 單說結論比較抽象，為了方便理解，我給出下圖。同時提醒大家，做ACM題目找不到思路的時候，嘗試一下畫圖來理清思路。

當然，更好的方式是在演算紙上畫圖，思路有了，代碼很自然就寫出來了。AC代碼如下：

public class FindMinimumInRotatedSortedArray {
    public int findMin(int[] num) {
    	if (num == null || num.length == 0) {
    		return 0;
    	}
    	
    	int left = 0, right = num.length - 1, min = num[left], mid = 0;
    	
    	while (left < right) {
    		mid = (left + right) / 2;
    		
    		if (mid == left || mid == right) {
    			break;
    		}
    		
    		if (num[left] < num[mid]) {
    			min = Math.min(min, num[left]);
    			left = mid + 1;
    		} else if (num[mid] < num[right]) {
    			min = Math.min(min, num[mid]);
    			right = mid - 1;
    		}
    	}
    	
    	min = Math.min(num[left], min);
    	min = Math.min(num[right], min);

    	return min;
    }
}