剑指Offer 11. 旋转数组的最小数字

发表于 | 更新于 | 分类于 | 阅读次数：

解答1[Java]：

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
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        int index1 = 0;
        int index2 = array.length - 1;
        int indexMid = 0;

        if (array.length == 0) {
            return 0;
        }

        while (array[index1] >= array[index2]) {
            if (index2 - index1 == 1) {
                indexMid = index2;
                break;
            }

            indexMid = (index1 + index2) / 2;

            if (array[index1] == array[indexMid] && array[indexMid] == array[index2]) {
                return minSequentialSearch(array);
            }

            if (array[indexMid] >= array[index1]) {
                index1 = indexMid;
            } else if (array[indexMid] <= array[index2]) {
                index2 = indexMid;
            }
        }

        return array[indexMid];
    }

    private int minSequentialSearch(int[] array) {
        int indexMin = 0;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[indexMin]) {
                indexMin = i;
            }
        }

        return array[indexMin];
    }
}

时间复杂度

时间复杂度为对数级别 $O(logN)$。

解答2[Java]：时间复杂度 $O(n/2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0) {
            return 0;
        }

        int min = array[0];

        for (int i = 1; i < array.length; ++i) {
            if (array[i] < min) {
                return array[i];
            }
        }

        return min;
    }
}

思路

旋转之后，从左向右对比两个相邻的数，总会找到一组数，第一个数大于第二个数，那么第二个数就是最小值。因为第二个数往后的所有数就是旋转操作移到最后的一系列数。