單調旋轉數組的TopK問題

問題描述：輸入一個單調旋轉後的數組，求該數組中的第k小的元素。

分析：很多人看到這個題目會有點懵，可能讀者不知道什麼是旋轉數組，我先解釋下兩個概念，            

        旋轉數組的定義：把一個數組的前幾項元素移動到數組的末尾，稱之為數組的旋轉。

        單調旋轉數組的定義：如果數組在旋轉之前是一個單調數組，則旋轉之後稱之為單調旋轉數組。

        為了友善解釋，這裡我以單調非遞減的旋轉數組為例進行解釋，其他類型可以通過這個例子類推。

        解法一：最簡單的方法就是從頭到位掃描一遍，求出小的元素下标，進而推算出第k小的元素下标，即可得到答案。

                   但是這樣做的時間複雜度為O(n).還可以尋求更快的解法。

        解法二：充分利用數組的單調性質解題，可以發現旋轉之後的數組可以劃分為兩個單調子數組，其中一個單調子數組所有的元素都大于等于另一                    個數組中的元素。

                   并且最小的元素正好是兩個元素的分解點，這樣就可以使用二分查找法進行查找。

                   可以設定三個指針left,right,mid分别指向數組頭元素、尾元素和中間元素的下标。利用中間元素去和頭元素比較，有兩種情況：

                              如果a[mid]>=a[left]，則令left=mid

                              如果a[mid]<a[left]，則令right=mid

                             然後再重新計算mid，就這樣一直循環去做，直到left+1==right停止，此時rigth就是最小元素下标，再根據k計算出第k小元                               素的下标即可。

                   此方法的時間複雜度為O(logn)。

        對比：很明顯解法二比解法一要快，但是要求數組必須是單調數組，而解法一可以用于所有的旋轉數組。由于解法一，比較簡單，我就不再程式設計                 實作了，我主要對解法二去程式設計實作。

                對于一般的測試樣例，解法二都沒問題，但是對于特殊的測試樣例，卻出現了問題。

                例如：1，0，1，1，1和1，1，1，0，1可以發現結果不正确，是以需要加以改進，如果left,right,mid所指元素都相等，解法二無能為                  力，需要使用解法一求解。

        我們可以在程式中對待這一特定條件去單獨判斷即可。

        另外解法二還可以進一步優化，如果a[left]<a[right]，我們直接就可以求出a[left]就是最小的元素，進而根據k求出第k小的元素。

        具體的Java代碼如下，代碼寫法都比較通用，讀者可以很容易的轉化為其他語言實作。

public class Main{
    public static void mintopk(int a[],int k){
    	if(a==null ||k<=0 ||k>a.length)                      //如果數組不存在或者k不符合要求，則直接結束
    		{ System.out.println("不存在");
    		  return ;
    		}
    	int p;                                              //用來表示mintopk數的下标
    	int left=0,right=a.length-1,mid=(left+right)/2;     //求出起初的開始、結束和中間元素下标
    	if(a[mid]==a[left] && a[mid]==a[right])             //如果三個下标所指元素相等，則從頭開始掃描
    		for(int i=1;i<a.length;i++)
    			if(a[i-1]>a[i])
    			{   p=i+k-1;
    				if(p>a.length-1)p=p-a.length;           //求出mintopk的下标 
    				System.out.println(a[p]);
    				return;
    			}
    	if(a[left]<a[right])                                //如果頭元素小于尾元素，則表明left所指為最小元素
    	{
    		p=left+k-1;
    		if(p>a.length-1)p=p-a.length;
        	System.out.println(a[p]);
        	return;
    	}
    	
    	while((left+1)!=right)                              //利用三個指針進行查找
    	{   
    		if(a[mid]>=a[left])left=mid;
    		else right=mid;
    		mid=(left+right)/2;
    	}
    	p=right+k-1;
		if(p>a.length-1)p=p-a.length;
    	System.out.println(a[p]);
    }
	public static void main(String[] args) {
		// TODO 自動生成的方法存根
		int a[]={3,4,5,1,2};
		int k=5;
        mintopk(a,k);
	}

}
           

輸出結果為：

5

注意：代碼中我隻寫了一組測試例子，讀者可以下載下傳代碼自行驗證。