剑指offer-1：旋转数组的最小数字

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

2、我的解答：

import java.util.ArrayList;
/*
本题考察重点：分类思想
        非减排序即包括递增排序和全等
*/
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int count = 0;
        int result = 0;
        if(array.length==0){
            return result;
        }
        for(int i=0;i<array.length-1;i++){
            if(array[i]>array[i+1]){
               result = array[i+1]; 
            }
            if(array[i]==array[i+1]){
               count++; 
            }
        }
        if(count==array.length){
            result = array[0];
        }
        return result;
    }
}

3、思考：我的解答没有考虑到旋转数组和原数组相同的情况，而且从头开始对数组进行遍历，时间复杂度O(n)。

4、优质解答：
1）内置排序工具
　　利用 Arrays 工具类里的排序函数，内置实现是三项切分快排，默认的排序规则是从小到大，排序后的数组第一个值就是最小值
代码：

import java.util.*;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int n = array.length;
        if(n == 0){
            return 0;
        }
        Arrays.sort(array);
        return array[0];
    }
}

2）二分查找
a. 注
　　非递减序列并不能找到最小值，因为对于{3, 3, 3, 3, 3, 1, 3} 和 {3, 1,3, 3, 3, 3, 3}，二分法并不能判断范围向哪边收缩
b. 分析
　　二分查找用于查找有序的数组中的值，题目所给数组在两段范围内有序，我们可以将给定数组分为两种情况：
　　其实并没有旋转，例如 {1,2,3,4,5}，旋转后也是 {1,2,3,4,5}，这样可以直接使用二分查找
　　如题所示，旋转了一部分，例如 {1,2,3,4,5}，旋转后为 {3,4,5,1,2}，需要限定特殊条件后使用二分查找
　　当数组如情况 1，有个鲜明的特征，即数组左边元素 < 数组右边元素，这时我们直接返回首元素即可
　　当数组如情况 2，此时有三种可能找到最小值：

　　标为 n+1 的值小于下标为 n 的值，则下标为 n+1 的值肯定是最小元素
　　下标为 n 的值小于下标为 n-1 的值，则下标为 n 的值肯定是最小元素
　　由于不断查找，数组查找范围内的值已经全为非降序（退化为情况1）
　　再讨论每次二分查找时范围的变化，由于情况数组的情况 1 能直接找到最小值，需要变化范围的肯定是情况 2：

　　当下标为 n 的值大于下标为 0 的值，从 0 到 n 这一段肯定是升序，由于是情况 2，最小值肯定在后半段
　　当下标为 n 的值小于下标为 0 的值，从 0 到 n 这一段不是升序，最小值肯定在这一段
c. 代码

import java.util.*;
public class Solution {
    public int minNumberInRotateArray(int [] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[l] < nums[r]) {
                return nums[l];
            }
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            if (nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return 0;
    }
}

d. 复杂度
时间复杂度：O(logn)
空间复杂度：O(1)