C++剑指offer——旋转数组的最小数字_c++剑指offer寻找旋转排序数组中的最小值

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

什么是非递减排序的数组？

做这道题之前我们要搞清楚几个概念。
递增排序：1，2，3，4，5，6…
递减排序：9，8，7，6，5，4…
非递增排序：9，8，8，6，4，4，2，1…
非递减排序：1，3，3，4，5，6，6，7…

解题思路

旋转数组，听起来很神秘，我们来看几个例子吧：
（1）
原数组：1，3，3，4，5，6，6，7
任意旋转数组：4，5，6，6，7，1，3，3
（2）
原数组：2，2，4，4，6，6，8，8
任意旋转数组：6，6，8，8，2，2，4，4
（3）
原数组：1，2，3，4，5，6，7，8
任意旋转数组：2，3，4，5，6，7，8，1
（4）
原数组：2，3，3，3，5，5
任意旋转数组：2，3，3，5，5

由此可见，所谓的旋转数组就是把原数组的前若干的元素放到末尾。如果若干个元素为0，那么第一个元素即为最小值。但如若干个元素大于等于1，那我们并不知道他在哪，
解法一：遍历数组
令当前的最小值为输入数组的第一个元素，从头往后找，根据非递减排序数组和旋转数组的特性，只要找到一个元素比他小，查找结束，返回查找到的值即可。时间复杂度O（N）。

代码：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) 
    {
        if(rotateArray.size()==0)
            return 0;
        int tempmin=rotateArray[0];
        for(int i=1;i<rotateArray.size();i++)
        {
            if(rotateArray[i]<tempmin)
            {
                tempmin=rotateArray[i];
                break;
            }
        }
        return tempmin;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法二：二分查找
显然这道题给的是一个有序的数组，直接查找不是最优的，可以进行优化采用二分查找。
举几个例子来推导解题细节（请记住题干的数组有序、某个点旋转这两个条件）：

arr[left] < arr[right]: 直接返回arr[left]。例如：1 2 3 4 5
arr[left] < arr[mid]: 说明从数组下标范围为[left, right]的元素是递增的，此时最小值只可能出现在[mid + 1, length)范围内。例如:4 5 1 2 3
arr[mid] < arr[right]: 说明从数组下标范围为[mid, right]的元素是递增的，此时最小值只可能出现在[left, mid] 范围内。注意，这里不能跳过下标mid。例如：3 3 3 4 5
其他情况，此时arr[mid] = arr[right] = arr[left]: 移动 left，缩小范围即可。例如：1 1 1 0 1
时间复杂度：O（logN）

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) 
    {
        if(rotateArray.size()==0)
            return 0;
        int low=0;
        int high=rotateArray.size()-1;
        while(low<high)
        {
            int mid=(low+high)/2;
            if(rotateArray[low]<rotateArray[high])
                return rotateArray[low];
            else if(rotateArray[mid]>rotateArray[low])
                low=mid+1;
            else if(rotateArray[mid]<rotateArray[high])
                high=mid;
            else
               low++;
        }
       return rotateArray[low];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23