一题一算法2018-02-08（旋转数组的最小数字）

题目：旋转数组的最小数字

题目描述：

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

题目思考：

首先，我们看到的非递减排序数组，实质上就是一个递增数组，一个递增数组将前面的一部分挪到后面去，这样就形成了两个递增的数组，前面一个数组中的所有元素都要比后一个大，那么问题就有了实质的变化，就是求这两个数组的分界线，此时整个数组的前一个元素大于后面一个元素的时候我们就可以知道，此时后面一个元素就是整个数组的最小值。

题目思路一：

最简单最之际的方法，也是我们最先想到的，但是却是最不推荐的，直接遍历比较大小。

题目思路二：

题目思考中的方式，循环遍历比较数组中前后两个元素，当遇到后一个比前一个小的时候，将后一个返回此时就是最小的元素。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0)
            return 0;
        for(int i = 0; i < rotateArray.size()-1; i++){
            if(rotateArray[i]>rotateArray[i+1]){
                return rotateArray[i+1];
            }
        }
        return rotateArray[0];
    }
};

题目思路三：

此种解法是从二分法出来的，通过二分法不断逼近最小的值，二分法从时间复杂度上来说是O(log(n)),而思路二的时间复杂度是O(n)，这种方式来说更加快捷。

---

1、先判断数组是否为空，为空返回0；
2、我们定义beg、end、mid三个指针分别指向数组的头、尾、中部；
3、判断数组是否旋转，就是array[beg]>array[end]，当出现这种状况的时候就说明数组旋转，没有的话就说明数组没有旋转，此时我们只输出array[0]即可。
4、当array[mid]>=array[beg]的时候，说明从beg到mid这部分还是递增的数组，那么此时beg= mid，将数组的范围缩小，变成mid～max，继续循环。
5、当array[mid]<=array[end]的时候，说明从mid到end这部分是递增的数组，此时end = mid，将数组的范围缩小，变成beg～mid，继续循环。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0)
            return 0;
        int beg = 0;
        int end = rotateArray.size() - 1;
        int mid =  0;
        while(rotateArray[beg] >= rotateArray [end]){
            
            if((end - beg) == 1){
                mid = end;
                break;
            } 
            mid = (end + beg)/2;
            if(rotateArray[beg] <= rotateArray[mid]){
                beg = mid;
            }
            if(rotateArray[end] >= rotateArray[mid]){
                end = mid;
            }
            
        }
        return rotateArray[mid];
    }
};

此思路存在的容易犯错的地方：因为数组是分成2段的，我们只能知道这两段的单调性，数组分成前后两半段递增，所以我们只能分别判断array[beg] 和 array[end]同array[mid]大小比较，这样我们才能判断其单调性，单调递增就是mid这个值不断逼近最小值的方法。

思路四：

看到题干我们知道数组书vector，我们用STL的函数将数组排序，直接输出array[0]即可。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        sort(rotateArray.begin(),rotateArray.end());
        return rotateArray[0];
    }
};

题目延伸：

给定一个有序数组，如{1,2,3,4,5,6,7,8,9}，我们将对这个数组进行选择，未知从什么位置旋转。下面给出一个可能的旋转结果。如{4,5,6,7,8,9,1,2,3}，我们可以理解为它从元素4位置开始旋转。之后给定一个指定的数字n，让我们从{4,5,6,7,8,9,1,2,3}这个数组中找出它的位置，要求时间复杂度尽可能的低。

延伸思路一：

从头开始遍历数组比较大小，返回n的位置。

延伸思路二：

使用STL的方法find()

延伸思路三：二分法

我可以使用上面类似的方法：

解题的思路和上面类似，分段判断，然后二分法逼近。

int search(int n,int[] array){
        int low = 0;        
        int high = array.length-1;
        while(low<=high){
            int middle = (low+high)/2;
            if(array[middle]==n) return middle;
            if(array[middle]>array[low]){  //left is order
                if(n<=array[middle]&&n>=array[low]){
                    high = middle-1;
                }else {
                    low = middle+1;
                }
            }else {         
                if(n>=array[middle]&&n<=array[high]){
                    low = middle+1;
                }else {
                    high = middle-1;
                }
            }
        }
        return -1;  
    }