解答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;
}
}
|
思路
旋转之后，从左向右对比两个相邻的数，总会找到一组数，第一个数大于第二个数，那么第二个数就是最小值。因为第二个数往后的所有数就是旋转操作移到最后的一系列数。