題目描述

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

解題思路

{3,4,5,1,2}為{1,2,3,4,5}的旋轉，前半部分始終大于等于后半部分，符合部分有序。仍然可以使用二分查找法，可判斷中間位置在前半部分還是在后半部分，如果在前半部分則min 在后半部分，否則在前半部分。這樣進行二分查找。
但是有特殊情況，當為這種情況時{1,1,1,0,1}或者{1,0,1,1,1}使用二分查找不會得到正確的結果，這種情況只能使用順序查找了。

解題代碼

#include <vector> #include <iostream> using namespace std; /* 題目描述 把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請返回0。 */ class SolutionMinNum { public:int minNumberInRotateArray(vector<int> rotateArray) {if (rotateArray.size() == 0)return 0;int low = 0;int high = rotateArray.size()-1;int mid = low;while (rotateArray[low] >= rotateArray[high]){if (high - low == 1){mid = high;break;}int mid = (low + high)/2;//特殊情況，{1,1,1,0,1}(只使用二分查找碰見可以查找成功，會走第一個if) 或者 {1,0,1,1,1}(只使用二分查找失敗)需要使用順序查找if (rotateArray[low] == rotateArray[mid] &&rotateArray[mid] == rotateArray[high]) return minInOrder(rotateArray, low, high);if (rotateArray[mid] >= rotateArray[low]) //最小值在后邊low = mid;else if (rotateArray[mid] <= rotateArray[high]) //最小值在前邊high = mid;}return rotateArray[mid];}int minInOrder(vector<int> & rotateArray, int low, int high) //順序查找最小值{int min = rotateArray[low];for (int i = low +1; i <=high; i++){if (min > rotateArray[i])min = rotateArray[i];}return min;} };int main(int argc, char *argv[]) {SolutionMinNum MinNum;vector<int> arr1 = { 3,4,5,1,2 };vector<int> arr2 = { 1, 1, 1, 0, 1 };vector<int> arr3 = { 1, 0, 1, 1, 1 };int min = MinNum.minNumberInRotateArray(arr1);cout << min << endl;min = MinNum.minNumberInRotateArray(arr2);cout << min << endl;min = MinNum.minNumberInRotateArray(arr3);cout << min << endl;system("pause");return EXIT_SUCCESS; }

運行測試

總結

以上是生活随笔為你收集整理的C/C++面试题—旋转数组的最小数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。