剑指offer-旋转数组的最小数字

2017/3/10 posted in  算法-数据结构  

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

解题思路

O(n)算法

数组遍历,如果a[i]<a[i-1],这该位置为旋转位置,即最小元素。

O(logn)算法

我们可以通过二分的思路,对上述问题进行优化。
我们发现,旋转之后的数组实际上可以划分为两个排序的子数组,而且后面的子数组的元素都小于等于前面的子数组的元素。而我们要找的这个最小元素,恰好是这两个数组的分界线。
和二分查找一样,我们分别用两个指针指向数组的第一个(start)和最后一个元素(end),在求一个中间指针指向数组的中间(mid = (start+end)/2):

  • 如果array[mid] >= array[end],说明分界值应该在数组的后半段,此时将start赋值为mid;
  • 如果array[mid] <= array[start],说明分界值应该在数组的前半段,此时将end赋值为mid;
  • 如果end-start == 1,说明array[end]为我们要找的分界值。
  • PS.如果 array[mid] == array[start] == array[end],此时只能通过遍历来实现。

代码示例

O(n)

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0){
            return 0;
        }
        for(int i=1;i<array.length;i++){
            if(array[i]<array[i-1]){
                return array[i];
            }
        }
        return array[0];
    }
}

O(logn)

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        int start = 0;
        int end = array.length - 1;
        while (end - start > 1) {
            int mid = (start + end) / 2;
            
            if(array[start] == array [mid] && array[mid] == array[end]){
                return order(array, start, end);
            }
            
            if( array[mid] >= array[end]){
                start = mid;
                continue;
            }
            if(array[mid] <= array[start]){
                end = mid;
                continue;
            }
        }
        return array[end];
    }
        
    public int order(int[] array,int start,int end){
        for(int i = start+1;i<=end;i++){
            if(array[i]<array[i-1]){
                return  array[i];
            }
        }
        return array[start];
    }
}