旋轉數組的最小數字——II

題目鏈接

注：此題是昨天旋轉數組的最小數字——I的拓展延伸，昨天題目數組的條件是不會存在重復元素，而本題數組的元素可以重復，因此建議先做前面一題，進行思考，這樣求解這一題的過程就會容易理解許多。

---

旋轉數組的性質

由旋轉數組的最小數字——I我們知道了：

以數組最右側數據val為參考對象，最小值右側的數一定小于val，最小值左邊的數一定大于val

可以得到以下圖像：

而今天這一題多了一個條件：數組中可能存在重復元素。我們需要考慮的情況又復雜了一點：

以數組最右側數據val為參考對象，最小值右側的數一定等于小于val，最小值左邊的數一定大于等于val

我們同樣用二分法來解決：

• 同樣，我們設左邊界為left，右邊界為right，區間的中間下標為mid

• 如果nums[mid] > nums[right]，和原來一樣，最小值一定不在左側區域，left = mid + 1

• 如果nums[mid] < nums[right]，和原來一樣，最小值一定不在右側區域（但可能就是mid位置的值），right = mid

• 如果nums[mid]==nums[rihgt]，這種情況就值得注意了，如下圖：

• 此時，nums[mid]可能在最小值的左邊，也可能在最小值的右邊，因此我們不能隨意地舍去mid左側的數據或者右側的數據。對于這種情況的處理，我們有兩種方法：

方法一：

不能隨意舍去mid左半部分或者右半部分是因為最小值到底是在mid的左邊還是右邊是不確定的，但是如果我們可以通過處理來確定最小值和mid的關系呢？

我們知道，數組旋轉后，其被分割成了兩串非遞減數列，而令我們困擾的就是諸如這種情況：[3,3,1,3]，[4,4,5,1,4,4,4,4,4]。那么我們可以刪除數組前面所有等于nums[right]的元素，使數組變成諸如[1,3]，[5,1,4,4,4,4]的形式，這樣當nums[mid]==nums[right]這種情況出現時，mid就一定會出現在最小值的右側，mid右側的數據也就可以刪除了。

實現代碼

int minArray(int* nums, int numsSize){int left = 0;int right = numsSize - 1;//刪除數組前面所有等于nums[right]的元素while (left < numsSize && nums[left] == nums[right])left++;while (left < right){int mid = (right - left) / 2 + left;//如果中間值大于最右邊的值，那么最小值一定在中間值的右邊if (nums[mid] > nums[right])left = mid + 1;//否則，最小值就在最右邊的值的左邊，也可能就是這個中間值elseright = mid;}return nums[right];
}

方法二

雖然我們不能隨意舍棄mid的左半部分或者右半部分，但是我們可以確定，無論nums[right]是不是最小值，都有它的一個替代品nums[mid]，因此我們可以刪除最右邊的數據nums[right]

實現代碼

int minArray(int* nums, int numsSize){int left = 0;int right = numsSize - 1;while (left < right){int mid = (right - left) / 2 + left;//如果中間值大于最右邊的值，那么最小值一定在中間值的右邊if (nums[mid] > nums[right])left = mid + 1;//如果中間值小于最右邊的值，那么最小值一定在中間值的左邊或者就是中間值else if (nums[mid] < nums[right])right = mid;//如果中間值等于最右邊的值，那么就刪除最右側元素else    right--;}return nums[left];
}