剑指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;
}