题目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：旋转数组的最小数字
* 来源：http://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
* 网址：http://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;
}
