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