剑指offer面试题8-旋转数组的最小数字

问题描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3, 4, 5, 1, 2}为数组{1, 2, 3, 4, 5}的一个旋转,该数组最小值为1。

解决思路

最简单的解决方法不过就是把数组遍历一遍,但是这种方式是一个时间复杂度为O(n)的算法,而且这个算法没有利用旋转数组的特性,不是最优解。

根据旋转数组的特性可知,旋转后的数组可以分为两个已排序数组,第一个已排序数组中所有值都大于第二个数组中的值,且这两个数组的分界线刚好是最小的元素。例如,问题描述中的旋转数组{3, 4, 5, 1, 2}就可以以最小元素1为分界线划分出两个数组:{3, 4, 5}、{ 1, 2}。由于给出的数组都是排序过的,则可以根据二分查找的思路去查询最小元素。

根据二分查找的思路,将指针p1指向数组中第一个元素,p2指向数组最后一个元素,找到中间元素mid。

此时,若mid大于等于p1所指向的元素,mid左侧则为递增序列,最小值应在mid右侧,将指针p1指向中间元素位置,然后进行下一轮查找;
若mid小于等于p2所指向元素,mid右侧则为递增序列,最小值应在mid左侧,将指针p2指向中间元素位置,然后进行下一轮查找。

移动p1或p2后,下次查询的范围就会缩小一半,时间复杂度则为O(logn)。

在按上述思路查找过程中,p1始终指向第一个递增数组中的元素,p2始终指向第二个递增数组中的元素。当p1指向第一个数组的最后一个元素,p2指向第二个数组第一个元素时,p2指向的元素则为最小元素,查找结束。因此,查找的结束条件为:p1、p2最终指向相邻的两个元素。

查找示例

以数组{3, 4, 5, 1, 2}为例。

第一步:p1指向数组第一个元素3,p2指向数组最后一个元素2,此时中间元素为5,5大于3,5左侧为递增序列,最小元素在5的右侧,将p1指向中间元素5。
第二步:p1指向5,p2指向2,此时中间元素为1,1小于5且小于2,1右侧为递增序列,最小元素在1的左侧,将p2指向中间元素1。

此时p1和p2指向了两个相邻元素,此时p2指向的元素1则为最小元素了。

特殊场景

场景1

根据旋转数组定义,需要把一个已排序数组最开始的若干个元素搬到数组的末尾,那假若将最开始的0个元素搬至数组末尾,那得到的数组即为原数组,也就是说数组本身就是该数组的一个旋转数组,此时按照上边的思路找到的元素不是最小元素。

解决方法就是在查找前,先判断下第一个元素是否大于等于最后一个元素,若大于或等于,则按上述方式查找即可;否则,第一个元素就是最小元素。

场景2

在上边的解决方法中,我们有一种情况未考虑,即中间元素既等于p1指向元素又等于p2指向元素。此时,我们不能确定中间元素的哪一侧是递增序列,此时只能使用逐一遍历的方式查找了。

例如数组{1,1,1,0,1}和{1,0,1,1,1}是数组{0,1,1,1,1}的旋转数组,此时p1、p2指向的元素及中间元素都为1。

代码

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
public int minNumberInRotateArray(int [] array) {
if(array == null || array.length == 0) {
return 0;
}

int index1 = 0;
int index2 = array.length-1;
int midIndex = index1;

//如index1 指向的元素小于 index2指向的元素,则数组已经是排序数组,直接返回midIndex
while(array[index1] >= array[index2]) {
if(index2 - index1 == 1) {
midIndex = index2;
break;
}

midIndex = (index1 + index2)/2;

//中间元素等于起始元素,等于末尾元素,应顺序查找
if(array[index1] == array[midIndex] && array[index2] == array[midIndex]) {
return findInOrder(array, index1, index2);
} else if (array[index1] <= array[midIndex]) {
index1 = midIndex;
} else {
index2 = midIndex;
}
}

if(midIndex == -1) {
System.out.println("error");
}

return array[midIndex];
}

private int findInOrder(int[] array, int start, int end) {
int temp = array[start];
for(int i=start+1; i<=end; i++) {
if(array[i] < temp) {
temp = array[i];
}
}
return temp;
}