11:旋转数组的最小数字

发表于 | 分类于

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

把一个数组最开始的若干个元素搬到数组的末尾， 我们称之数组的旋转。输入一个递增排序的数组的一个旋转， 输出旋转数组的最小元素。

举例说明

数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

思路

一. 顺序遍历$O(n)$

首先能想到的就是顺序遍历，数组中最小的元素即为整个旋转数组的最小元素，但算法时间复杂度为O(n)

二. 二分$O(logn)$

有序数组的查找大部分离不开二分。

由旋转数组的特性，因为经排序好的数组旋转得到的，所以由其特性可以知道，除了不旋转的情况（即原数组），旋转数组可以划分为两个排序的子数组，前面的子数组元素均大于后面的子数组元素，存在分界线，所以可以想到的就是利用二分查找法，实现时间复杂度为O(logn)

步骤

牢记：要求的是如果发生过旋转，第二个数组的第一个数。

1. 设置两个指针low,high

low指向数组的开始位置，也就是第一个数组的开始位置
high指向数组的终止位置，也就是第二个数组的结束位置
Mid在中点

2. 比较mid与low,high位置的数组值

一直逼近第二个数组的第一个数。

mid与low,high初始数组值关系

  1. 如果中间位置mid的数大于low指向的数，则mid在第一个数组中。故让low指向mid所指向的数，low指向的依然是数组1的数
  2. 如果中间位置mid的数小于high所指向的位置，则mid在第二个数组中。故让high指向mid指向的数，high指向的依然是数组2的数
  3. 知道low和high只差1（相邻），high指针的数组值就是所求

注意考虑以下几种情况的处理：

  1. 数组元素为空的情况（返回0）
  2. 数组元素只有一个的情况（返回该元素）
  3. 数组旋转0个元素，也就是没有旋转的情况，（最后返回mid对应的值，所以初始时令mid=low，遇到该情况while条件不成立，依然返回mid对应的值）
  4. 如果mid的数既等于p1位置数，又等于p2位置的数，这时候不能确定移哪个指针，就必须采用顺序查找的方法来寻找最小数
    如，排序数组为{0,1,1,1,1}，旋转数组为{1,0,1,1,1}或者{1,1,1,0,1}，当为这两种情况时，mid=low=high，无法确定最小的元素在左还是在右，所以这个时候就需要采用顺序查找的方式。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class _11 {
    public static int min(int[] arr) {
        if (arr == null||arr.length< 1) {
        	throw new RuntimeException("Invalid input.");
        }   
        if ( arr.length ==1) {
            return arr[0];
        }  
        int low = 0;// 开始处理的第一个位置
        int high = arr.length - 1;// 开始处理的最后一个位置
        int mid = low;// 设置初始值 
        // 确保low在前一个排好序的部分，high在排好序的后一个部分
        while (arr[low] >= arr[high]) {//没中while就返回mid(low)
            if (high - low == 1) {
                return arr[high];
            }
            mid = low + (high - low) / 2;
            // 如果三个数都相等，则需要进行顺序处理，从头到尾找最小的值
            if (arr[mid] == arr[low] && arr[high] == arr[mid]) {
                return minInorder(arr, low, high);
            }    
            if (arr[mid] >= arr[low]) {// 如果arr[mid]在前一个排好序的部分
                low = mid;
            }
            else if (arr[mid] <= arr[high]) {// 如果arr[mid]在后一个排好序的部分
                high = mid;
            }
        }
        return arr[mid];
    }
 
    private static int minInorder(int[] numbers, int start, int end) {//顺序处理
        int result = numbers[start];//想象一个pivot拉低整条线
        for (int i = start + 1; i <= end; i++) {
            if (result > numbers[i]) {
                result = numbers[i];
            }
        }
        return result;
    }
 
    public static void main(String[] args) {
        // 典型输入，单调升序的数组的一个旋转
        int[] array1 = {3, 4, 5, 1, 2};//1
        System.out.println(min(array1));
        // 有重复数字，并且重复的数字刚好的最小的数字
        int[] array2 = {3, 4, 5, 1, 1, 2};//1
        System.out.println(min(array2));
        // 有重复数字，但重复的数字不是第一个数字和最后一个数字
        int[] array3 = {3, 4, 5, 1, 2, 2};//1
        System.out.println(min(array3));
        // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
        int[] array4 = {1, 0, 1, 1, 1};//0
        System.out.println(min(array4));
        // 单调升序数组，旋转0个元素，也就是单调升序数组本身
        int[] array5 = {1, 2, 3, 4, 5};//1
        System.out.println(min(array5)); 
        // 数组中只有一个数字
        int[] array6 = {2};//2
        System.out.println(min(array6));
        // 数组中数字都相同
        int[] array7 = {1, 1, 1, 1, 1, 1, 1};//1
        System.out.println(min(array7));
        // 输入NULL
        System.out.println(min(null));//java.lang.RuntimeException: Invalid input.
    }
}

输出：

1
2
3
4
5
6
7
8
1
1
1
0
1
2
1
Exception in thread "main" java.lang.RuntimeException: Invalid input.
> >