剑指offer第六题。

题目描述

一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

解题思路

当我们看到关键字“非减排序的数组"的时候,我们要想到这题目的最优解可能是用二分查找法。

我们知道,二分查找法适用于有序数组的查找,这里对这个非减排序的数组进行了旋转,那么旋转之后这个数组的一个明显特征是:前面的一段序列必然大于等于后面的一段序列。

这题目可以认为是二分查找法的变种题目,下面我们来具体分析一下编程思路。

我们可以找一个基准数,比如数组的最优一个元素target,我们比较中间元素比如叫做arr[mid]和这个target的大小:

  • 如果arr[mid]>target:那么表明截取的时候,后面比前面长,那么最小值必然存在于索引mid的后面
  • 如果arr[mid]<target:那么表明截取的时候,前面比后面长,那么最小值必然存在于索引mid的前面(此时应该包含mid对应的元素,因为极限情况比如只有两个元素,那么反转之后前面可能比后面大,如果不包含这个mid就错了)
  • 如果arr[mid]=target:这个时候元素组比如为[0,1,1,1,1],那么旋转之后可能为 [1,0,1,1,1] 或者[1,1,1,0,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
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0){
return 0;
}
if(array.length == 1){
return array[0];
}

int start = 0;
int end = array.length - 1;
while(start <= end){
int mid = start + (end - start)/2;
if(array[mid] > array[end]){
start = mid + 1;
}else if(array[mid] < array[end]){
end = mid;
}else{
end--;
}
}
return array[start];
}
}