程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode]Find Minimum in Rotated Sorted Array,解題報告

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

編輯:關於C++

前言

今天來杭州參加百阿培訓,住在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;
    }
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved