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