面试题8：旋转数组的最小值（Leetcode-153,154）_循环数组最小值 leetcode

题目：把一个数组最开始的若干元素搬到数组的末尾，称为数组的旋转。
输入一个递增数组的一个旋转，输出其最小值。假设这个递增数组中没有重复元素
例如数组{3,4,5,1,2}是{1,2,3,4,5}的一个旋转，最小值是1。

一. O（N）解法

最直观的解法就是遍历数组，找到一对相邻的数，前数比后数大，则后数就是最小值。
如果未找到这样一对相邻的数，那么这个数组就未旋转，最小值即为第一个数。

int findMin(vector<int>& nums) {
    int size = nums.size();   
    for(int i=1; i<size; ++i)
    {
        if(nums[i] < nums[i-1])
        {
            return nums[i];
        }
    }    
    return nums[0];
}
1
2
3
4
5
6
7
8
9
10
11

二. O（logN）解法

显然，这种解法未利用旋转数组的特性，对于旋转数组，最小的数满足以下两个条件：
（1）在一个递减序列中
（2）必定是相邻的两个数之间的小者
(3) 如果未找到递减序列，那么说明数组未旋转，第一个数就是最小数
我们可以用双指针，分别从两边遍历到中间的方法找到这个最小数。分析如下：

int minNumberInRotateArray(vector<int> a) {
    int i = 0, j = a.size()-1;
    while (i < j) {
      if (a[i] > a[i+1]) {
        return a[i+1];
      }

      if (a[j-1] > a[j]) {
        return a[j];
      }
      ++i;
      --j;
    }
    return a.empty() ? 0 : a[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三. 旋转数组中存在重复元素（Leetcode-154）

如果旋转数组为{10,1,10,10}。
O（logN）的解法就无法使用了。
只能用第一种O（N）解法。