旋转数组的最小数字

题目描述

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

代码格式要求

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
    
    }
}

非递减数组是指一个数组中的元素要么递增要么相等。

解题一 -暴力法直接查找

1.思路
在一个非递减组数的旋转数组中，只需判断如果前一个数组大于后一个数组，那么后一个数组即为要找的旋转数组中的最小元素。如果旋转数组{6,7,1,3,4,4}，当7大于1时，即可判断出1位数组的最小元素。
2.代码

package jianzhi_offer;

public class Solution6_1 {
    public static int minNumberInRotateArray(int[] array) {
        int n=array.length;
        if(n==0) {
            return 0;
        }
        for(int i=0;i<n-1;i++) {
            if(array[i]>array[i+1]) {
                return array[i+1];
            }
        }
        return array[0];
    }
    public static void main(String[] args) {
        int[] a= {8,9,2,3,5};
        System.out.println(minNumberInRotateArray(a));  
    }
}

运行结果

image.png

3.复杂度
时间复杂度：O(n)
空间复杂度：O(1)

解题二-排序

1.思路
利用 Arrays 工具类里的排序函数，默认的排序规则是从小到大，排序后的数组第一个值就是最小值。
*通过题意可以了解到，只需要输出旋转后数组最小元素就行了，所以直接给数组进行排序
*数组的一个元素就是最小元素，最后输出即可，Arrays.sort()的排序时间复杂度是根据数组长度来判断
*基本类型是quick sort排序，对象类型是优化过后 merge sort，时间复杂度是O(nlgn) 空间复杂度O(1)

2.代码

import java.util.Arrays;

public class Solution6_2 {
    public int minNumberInRotateArray(int[] array) {
        int n=array.length;
        if(n==0) {
            return 0;
        }
        Arrays.sort(array);
        return array[0];
    }
}

3.复杂度
时间复杂度：O(nlogn)
空间复杂度：O(1)

解题三-利用优先队列

1.思路
将数组元素挨个放进优先队列，优先队列默认为最小堆，弹出的第一个数就是整个数组的最小值。
2.代码

import java.util.PriorityQueue;

//优先队列
public class Solution6_3 {
    public int minNumberInRotateArray(int[] array) {
        if(array.length==0) {
            return 0;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<Integer>();
        for(int i=0;i<array.length;i++) {
            queue.add(array[i]);
        }
        return queue.poll();
    }
}

3. 复杂度
   时间复杂度：O(n)
   空间复杂度：O(n)

解题四-二分查找法

1.解析
本题的一个简单算法就是从左到右遍历，由于是递增的，直到找到一个小的数就可以停止了但是这种方法速度相对太慢，所以可以采用二分法的思想采用二分法的思想，定义一个left和right逐步缩小范围，最终确定最小的数.
2.代码

package jianzhi_offer;
//二分排序
public class Solution6_4 {
    public static int minNumberInRotateArray(int[] array) {
        if(array.length==0) {
            return 0;
        }
        ///定义左边界
        int left=0;
        //定义右边界
        int right=array.length-1;
        //当左小于右的时候，说明范围还没缩小完毕
        while (left<right) {
            int mid=(left+right)/2;
            //如果大于的话，说明最小值在右边，更新左边界值
            if(array[mid]>array[right]) {
                left=mid+1;
            //判断是否等于，让right-1，继续遍历
            }else if(array[mid]==array[right]){
                right=right-1;
            }else {
                //判断是否小于，小于的话更新有边界值
                right=mid;
            }
        }
        //最后返回right或者left
        return array[right];
    }
    public static void main(String[] args) {
         int  []a= {3,4,5,1,2};
         System.out.println(minNumberInRotateArray(a));
        }
}

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

二分查找法

参考解答区“leetcold”的解答，进行图示分析
分析：二分查找变种，没有具体的值用来比较。那么用中间值和高低位进行比较，看处于递增还是递减序列，进行操作缩小范围。

• 处于递增：low上移
• 处于递减：high下移（如果是high-1，则可能会错过最小值，因为找的就是最小值）
• 其余情况：low++缩小范围

image.png

• 特殊情况：

image.png

代码

`int` `minNumberInRotateArray(vector<``int``> rotateArray) {`

`if``(rotateArray.empty())`

`return` `0``;`

`int` `low =` `0``;`

`int` `high = rotateArray.size() -` `1``;`

`int` `mid =` `0``;`

`while``(low < high){`

`// 子数组是非递减的数组，10111`

`if` `(rotateArray[low] < rotateArray[high])`

`return` `rotateArray[low];`

`mid = low + (high - low) /` `2``;`

`if``(rotateArray[mid] > rotateArray[low])`

`low = mid +` `1``;`

`else` `if``(rotateArray[mid] < rotateArray[high])`

`high = mid;`

`else` `low++;`

`}`

`return` `rotateArray[low];`

`}`