C++版 - 剑指offer 面试题8：旋转数组的最小数字 题解
C++版 - 剑指offer 面试题8：旋转数组的最小数字 题解
面试题8：旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个已从小到大排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。(要求不能直接遍历数组来求解.)
提交网址： http://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159
或 http://ac.jobdu.com/problem.php?pid=1386
时间限制：1 秒 内存限制：32 M 特殊判题：否 提交：7633 解决：1686
题目描述：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
输入：
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为一个整数n(1<= n<=1000000)：代表旋转数组的元素个数。
输入的第二行包括n个整数，其中每个整数a的范围是(1<=a<=10000000)。
输出：
对应每个测试案例，
输出旋转数组中最小的元素。
牛客网OJ 样例输入：(对于C++提交：vector<int> rotateArray)3 4 5 1 2 九度OJ 样例输入：53 4 5 1 2样例输出：1
分析：
这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是O(n)。但这个思路没有利用旋转数组的特性，我们应该能找到更好的解法。 注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还可以注意到最小的元素刚好是这两个子数组的分界线。我们试着用二分搜索法的思路寻找这个最小的元素，时间复杂度为O(log n)。
牛客网OJ AC代码：
#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray)
{
if(rotateArray.size() == 0) return 0; // 输入的是空数组
int low = 0, high = rotateArray.size() - 1;
int mid;
if(rotateArray[low] < rotateArray[high]) return rotateArray[low]; // 输入的是完全旋转数组
while(rotateArray[low] >= rotateArray[high]) // 输入的是部分旋转数组
{
mid =(low + high) / 2;
if(high - low == 1) return rotateArray[high];
// 当low和high两个指针相邻时候，就找到了最小值，也就是右边序列的第一个值
if(rotateArray[low] == rotateArray[mid] && rotateArray[mid] == rotateArray[high])
{ // 当rotateArray[low]、rotateArray[high]、rotateArray[mid]三者相等时，
// 无法确定中间元素是属于前面还是后面的递增子数组，只能顺序查找
int min = rotateArray[low];
for(int i = low + 1; i <= high; i++)
min = rotateArray[i]<min ? rotateArray[i] : min;
return min;
}
if(rotateArray[low] <= rotateArray[mid]) low = mid;
// 中间元素位于前面的递增子数组, 且此时最小元素位于中间元素的后面
else high = mid;
// 中间元素位于后面的递增子数组, 且时最小元素位于中间元素的前面
}
return rotateArray[low];
}
};
// 以下为测试
int main()
{
Solution sol;
vector<int> vec1={3,4,5,1,1,2};
vector<int> vec2={1,1,2,3,4,6};
int res1 = sol.minNumberInRotateArray(vec1);
int res2 = sol.minNumberInRotateArray(vec2);
printf("%d\n", res1);
printf("%d\n", res2);
return 0;
}按《剑指offer》2014版中的思路写出的代码：
#include <cstdio>
#include <vector>
using namespace std;
class Solution{
public:
int minNumberInRotateArray(vector<int> rotateArray)
{
int size = rotateArray.size(); // 输入的是空数组
if(size == 0) return 0;
int left = 0, mid = 0, right = size - 1;
if(rotateArray[left] < rotateArray[right]) return rotateArray[left]; // 输入的是完全旋转数组
while(rotateArray[left] >= rotateArray[right]) // 输入的是部分旋转数组
{
if(right - left == 1) // 分界点
{
mid = right;
break;
}
mid = (right + left) / 2;
if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid])
{
// 顺序寻找最小值
int min = rotateArray[left];
for(int i = left + 1; i <= right; i++)
min = rotateArray[i]<min ? rotateArray[i] : min;
return min;
}
// 中间元素位于前面的递增子数组, 且此时最小元素位于中间元素的后面
if(rotateArray[mid] >= rotateArray[left]) left = mid;
// 中间元素位于后面的递增子数组, 且时最小元素位于中间元素的前面
else right = mid;
}
return rotateArray[mid];
}
};
// 以下为测试
int main()
{
Solution sol;
vector<int> vec1={3,4,5,1,1,2};
int res1 = sol.minNumberInRotateArray(vec1);
printf("%d\n", res1);
return 0;
}