523
[劍指Offer]10.旋轉數組的最小數字
題目1386：旋轉數組的最小數字
- 題目描述：
-
把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。
- 輸入：
-
輸入可能包含多個測試樣例，對於每個測試案例，
輸入的第一行為一個整數n(1<= n<=1000000)：代表旋轉數組的元素個數。
輸入的第二行包括n個整數，其中每個整數a的範圍是(1<=a<=10000000)。
- 輸出：
-
對應每個測試案例，
輸出旋轉數組中最小的元素。
- 樣例輸入：
-
53 4 5 1 2
- 樣例輸出：
-
1
/*********************************
* 日期：2013-11-14
* 作者：SJF0115
* 題號: 題目1386：旋轉數組的最小數字
* 來源：https://ac.jobdu.com/problem.php?pid=1386
* 結果：AC
* 來源：劍指Offer
* 總結：
**********************************/
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int array[1000001];
//求旋轉數組最小值
int MInArray(int *array,int n){
int left = 0;
int right = n - 1;
int mid = 0;
//二分查找最小值
while(array[left] >= array[right]){
//如果相鄰right下標為最小值
if(right - left == 1){
mid = right;
break;
}
mid = (left + right) / 2;
//如果下標為left,right,mid的數值相等，隻能順序查找
if(array[left] == array[right] && array[left] == array[mid]){
int min = array[left];
//順序查找最小值
for(int i = left + 1;i <= right;i++){
if(min > array[i]){
min = array[i];
}
}
return min;
}
//mid 處於第一遞增排序序列 最小值在mid後麵
if(array[mid] >= array[left]){
left = mid;
}
//mid 處於第二遞增排序序列 最小值在mid前麵
else if(array[mid] <= array[right]){
right = mid;
}
}
return array[mid];
}
int main()
{
int i,n;
while(scanf("%d",&n) != EOF){
for(i = 0;i < n;i++){
scanf("%d",&array[i]);
}
printf("%d\n",MInArray(array,n));
}
return 0;
}
【溫故】
/*---------------------------------------
* 日期：2015-07-20
* 作者：SJF0115
* 題目: 10.旋轉數組的最小數字
* 結果：AC
* 網址：https://www.nowcoder.com/books/coding-interviews/9f3231a991af4f55b95579b44b7a01ba?rp=1
* 來源：劍指Offer
* 博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int size = rotateArray.size();
if(size == 0){
return 0;
}//if
int left = 0,right = size - 1;
int mid = 0;
// rotateArray[left] >= rotateArray[right] 確保旋轉
while(rotateArray[left] >= rotateArray[right]){
// 分界點
if(right - left == 1){
mid = right;
break;
}//if
mid = left + (right - left) / 2;
// rotateArray[left] rotateArray[right] rotateArray[mid]三者相等
// 無法確定中間元素是屬於前麵還是後麵的遞增子數組
// 隻能順序查找
if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]){
return MinOrder(rotateArray,left,right);
}//if
// 中間元素位於前麵的遞增子數組
// 此時最小元素位於中間元素的後麵
if(rotateArray[mid] >= rotateArray[left]){
left = mid;
}//if
// 中間元素位於後麵的遞增子數組
// 此時最小元素位於中間元素的前麵
else{
right = mid;
}//else
}//while
return rotateArray[mid];
}
private:
// 順序尋找最小值
int MinOrder(vector<int> &num,int left,int right){
int result = num[left];
for(int i = left + 1;i < right;++i){
if(num[i] < result){
result = num[i];
}//if
}//for
return result;
}
};
int main(){
Solution s;
//vector<int> num = {0,1,2,3,4,5};
//vector<int> num = {4,5,6,7,1,2,3};
vector<int> num = {2,2,2,2,1,2};
int result = s.minNumberInRotateArray(num);
// 輸出
cout<<result<<endl;
return 0;
}
最後更新：2017-04-03 14:54:04