旋转数组的最小数字

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        // 这里可以将数组分解为两部分
        // 这两部分均为 从小到大排序的数组，以 12345 为例
        // 会有 34512、45123 等

        // write code here
        // 先来判断一下数组为空的情况
        if(nums.length == 0) {
            return 0;
        }

        // 使用二分法来解决
        int start = 0;
        int end = nums.length - 1;
        // 这里是旋转数组，先来考虑第一种情况
        // 当这里的第一个元素的值 比 最后一个元素的值小
        // 对于上面的例子，可以断定这里的第一个值 就一定是 最小值
        if(nums[start] < nums[end]) {
            return nums[start];
        }

        // 之后通过 二分法来判断最小值
        // 先来说明没有重复值的情况
        // 不断的通过 左、右 侧加逼 
        // 最终会使得 start 在左侧部分的最大值(最后一个位置) 上
        // 并且会使得 end 在右侧部分上达到其中的 最小值(这个就是我们需要的值)
        // 此时 start 和 end 就是一个相邻的关系，所以对于 while 设定这样一个判断条件
        while(start != end-1) {
            int mid = (start + end) / 2;
            // 在这之中还需要处理多个重复数据的情况，并且处理三个指针重叠后的情况
            // 如题例：1,0,1,1,1
            if(nums[start] == nums[end] && nums[start] == nums[mid]) {
                // 这里定义一个方法专门来处理这个问题
                return minNum(nums,start,end);
            }
            if(nums[mid] >= nums[start]) {
                start = mid;
            }else if(nums[mid] <= nums[end]){
                end = mid;
            }
        }
        // 在完成上面的判断后，这里的 end 位置的值就是我们要找到的最小值
        return nums[end];
    }

    private int minNum(int[] nums, int start, int end) {
        // 这里需要注意的是，要将值设置为 当前重合处的值，不能设置为 0 ！！！
        int re = nums[start];
        for (int i=0; i < nums.length; i++) {
            if(re > nums[i]) {
                // 将这里的最小值记录下来并返回
                re = nums[i];
            }
        }
        return re;
    }
}

public int minNumberInRotateArray (int[] nums) {
        // write code here
        if(nums.length <= 0){
            return 0;
        }
        int rt = nums[0];
        for(int info : nums){
            if(rt > info){
                rt = info;
            }
        }
        return rt;
    }

不考虑二分是不是更快？

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        // write code here
        a(nums,0,nums.length-1);
        return nums[0];
    }
    public void a(int[] nums,int left,int right){
        if(left>=right)
            return;
        int mid=(left+right)/2;
        a(nums,left,mid);
        a(nums,mid+1,right);
        b(nums,left,mid,right);
    }
     public void b(int[] nums,int left,int mid,int right){
        if(nums[left]>nums[mid+1]){
            nums[left]=nums[mid+1];
        }
    }
}

import java.util.*;


public class Solution {
    //揪出L,M,R都相等的情况，然后就能二分
    //但是，[M]不能和[L]去对比，因为不一定就是旋转过的.
    //在旋转过的情况下， [L] > [M], 确实应该去右边二分
    //但是这种本来就有序的例子：[1, 2, 3, 4, 5, 6]就过不了
    //所以只能让[M]和[R]去比,
    //[M] > [R], 只有一种可能，转折点在右边，所以去右边二分
    //[M] < [R], 去左边二分，会发现不管是不是旋转过，都是对的
    //最后，返回的应该是[L], [R]中小的那个
    //还是因为可能本来就有序，
    //如果旋转过，L一定指向左子数组最后，R一定是右子数组最开始，那么返回R没错
    //如果本来有序，就会发现是不对的
    public int minNumberInRotateArray (int[] nums) {
        // write code here
        int L = 0, R = nums.length - 1, M = 0;
        int min = nums[M];
        while (L <= R) {
            M = L + ((R - L) >> 1);
            if (R - L == 1) {
                // M = R;
                break;
            }
            if (nums[L] == nums[M] && nums[M] == nums[R]) {
                while (R > L && nums[R - 1] == nums[R]) {
                    R--;
                }
                //L == M || [L] != [L + 1]
                if (R == L) {
                    return nums[R];
                } else {
                    R = R - 1;
                    continue;
                }
            }
            if (nums[M] > nums[R]) {
                L = M;
            } else {
                R = M;
            }

        }
        return Math.min(nums[L], nums[R]);
    }
}

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int min = Integer.MAX_VALUE;
        for(int arr : array){
            min = Math.min(min,arr);
        }
        return min;
    }
}

public int minNumberInRotateArray(int [] array) {
        int left=0;
        int right=array.length-1;
        //删除重复元素
        while(left!=right&&array[left]==array[right]){
            right--;
        }
        if(left==right||array[left]<array[right]){
            return array[left];
        }
        int num=array[left];
        while(left!=right){
            int mid=left+(right-left)/2;
            if(array[mid]>=num){//比基准大，往右走
                left=mid+1;
            }else{
                right=mid;//这里为什么不是mid-1
            }
        }
        return array[right];
    
    }