【剑指offer】旋转数组的最小数字 --Java实现

1. 暴力法直接寻找

1. 分析

在两段范围内都是非降序，当不符合这个规律时，就找到了最小数字

2. 代码

import java.util.ArrayList;
public class Solution {
    public 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];
    }
}

3. 复杂度

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

2. 排序

1. 分析

利用 Arrays 工具类里的排序函数，默认的排序规则是从小到大，排序后的数组第一个值就是最小值

2. 代码

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];
    }
}

3. 复杂度

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

3. 利用优先队列

1. 分析

将数组元素挨着丢进优先队列，优先队列默认为最小堆，弹出的第一个数就是整个数组的最小值

2. 代码

import java.util.*;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int n = array.length;
        if(n == 0){
            return 0;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0;i<n;i++){
            queue.add(array[i]);
        }
        return queue.poll();
    }
}

3. 复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

4. 二分查找法

0. 注

非递减序列并不能找到最小值，因为对于{3, 3, 3, 3, 3, 1, 3} 和 {3, 1,3, 3, 3, 3, 3}，二分法并不能判断范围向哪边收缩

1. 分析

二分查找用于查找有序的数组中的值，题目所给数组在两段范围内有序，我们可以将给定数组分为两种情况：

其实并没有旋转，例如 {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 这一段不是升序，最小值肯定在这一段

2. 代码

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;
    }
}

3. 复杂度

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