題目鏈接：旋轉(zhuǎn)數(shù)組的最小數(shù)字

文章目錄

• 1、題目描述
• 2、題目分析
• 3、代碼
• • 3.1 Java代碼
  • 3.2、C++代碼
• 4、總結(jié)

1、題目描述

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個非減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0。

2、題目分析

從頭遍歷到尾找到最小值這種low的方法就不說了，是個人都會！！！

旋轉(zhuǎn)之后的數(shù)組實際上可以劃分成兩個有序的子數(shù)組：前面子數(shù)組的大小都大于后面子數(shù)組中的元素

注意到實際上最小的元素就是兩個子數(shù)組的分界線。本題目給出的數(shù)組一定程度上是排序的，因此我們試著用二分查找法尋找這個最小的元素。如下圖：

思路：

（1）我們用兩個指針l_ndex,r_index分別指向數(shù)組的第一個元素和最后一個元素。按照題目的旋轉(zhuǎn)的規(guī)則，第一個元素應(yīng)該是大于最后一個元素的（沒有重復(fù)的元素）。
但是如果不是旋轉(zhuǎn)，第一個元素肯定小于最后一個元素。

（2）找到數(shù)組的中間元素。

如果中間元素大于第一個元素，則中間元素位于前面的遞增子數(shù)組，此時最小元素位于中間元素的后面。我們可以讓第一個指針l_index指向中間元素。

移動之后，第一個指針仍然位于前面的遞增數(shù)組中。

如果中間元素小于第一個元素，則中間元素位于后面的遞增子數(shù)組，此時最小元素位于中間元素的前面。我們可以讓第二個指針right指向中間元素。

移動之后，第二個指針仍然位于后面的遞增數(shù)組中。這樣可以縮小尋找的范圍。

比如當(dāng)上圖的情況，那么接下來的下一次循環(huán)過后，就是下圖的樣式：

（3）按照以上思路，第一個指針l_index總是指向前面遞增數(shù)組的元素，第二個指針r_index總是指向后面遞增的數(shù)組元素。

最終第一個指針將指向前面數(shù)組的最后一個元素，第二個指針指向后面數(shù)組中的第一個元素。

也就是說他們將指向兩個相鄰的元素，而第二個指針指向的剛好是最小的元素，這就是循環(huán)的結(jié)束條件。

特殊情況：

到目前為止以上思路很好的解決了沒有重復(fù)數(shù)字的情況。如果有重復(fù)數(shù)字情況呢？

我們看一組例子：｛1，0，1，1，1｝ 和 ｛1，1， 1，0，1｝ 都可以看成是非減排序的數(shù)組｛0，1，1，1，1｝的旋轉(zhuǎn)。

這種情況下我們無法繼續(xù)二分法，去解決這道題目。因為在這兩個數(shù)組中，第一個數(shù)字，最后一個數(shù)字，中間數(shù)字都是1。

第一種情況下，中間數(shù)字位于后面的子數(shù)組（綠色），第二種情況，中間數(shù)字位于前面的子數(shù)組（紫色）。

因此當(dāng)兩個指針指向的數(shù)字和中間數(shù)字相同的時候，我們無法確定中間數(shù)字1是屬于前面的子數(shù)組（紫色）還是屬于后面的子數(shù)組（綠色）。

也就無法移動指針來縮小查找的范圍。這時只能使用順序查找法查找。

3、代碼

3.1 Java代碼

import java.util.ArrayList; public class Solution {public int minNumberInRotateArray(int [] array) {int size = array.length;if(size==0)return 0;int l_index=0;int r_index=size-1;int m_index=-1;while(array[l_index]>=array[r_index]){if(r_index - l_index==1)break;//當(dāng)只有兩個數(shù)時，肯定是第二個數(shù)是最小數(shù)m_index=l_index+(r_index-l_index)/2;/* 如果左中右都相等，例如101111，則無法判斷，只能按順序查找 */if(array[l_index]==array[m_index] && array[m_index]==array[r_index])return MinInorder(array,l_index,r_index);if(array[m_index]>=array[l_index])l_index=m_index;else r_index=m_index;}return array[r_index];}/* 按順序查找 */int MinInorder(int [] array ,int l,int r){int min=array[l];for(int i=l;i<=r;++i){if(array[i]<min)min=array[i];}return min;} }

3.2、C++代碼

class Solution { public:int minNumberInRotateArray(vector<int> rotateArray) {int size = rotateArray.size();if(size == 0)return 0;int l_index = 0;int r_index = size - 1;int m_index = -1;while(rotateArray[l_index]>=rotateArray[r_index]){if(r_index - l_index == 1)break;m_index = l_index + (r_index-l_index)/2;/* 當(dāng)左中右都相等時，例如101111，無法判斷，只能順序查找 */if(rotateArray[l_index]==rotateArray[m_index] && rotateArray[m_index]==rotateArray[r_index])return MinInorder(rotateArray,l_index,r_index);if(rotateArray[m_index]>=rotateArray[l_index])l_index = m_index;else if(rotateArray[m_index]<=rotateArray[r_index])r_index = m_index;}return rotateArray[r_index];}int MinInorder(vector<int> rotateArray, int index1, int index2){int Min = rotateArray[index1];for (int i = index1 + 1; i < index2; i++){if (rotateArray[i] < Min){Min = rotateArray[i];}}return Min;} };

4、總結(jié)

注意二分查找的應(yīng)用與特殊情況的考慮

探討學(xué)習(xí)加：
qq：1126137994
微信：liu1126137994

總結(jié)

以上是生活随笔為你收集整理的【剑指offer - C++/Java】6、旋转数组的最小数字的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。