美文网首页
11:旋转数组的最小数字

11:旋转数组的最小数字

作者: stoneyang94 | 来源:发表于2018-09-10 11:22 被阅读0次

题目11:旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾, 我们称之数组的旋转。输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素。

举例说明

数组{3,4,5,1,2}{1,2,3,4,5}的一个旋转,该数组的最小值为1。

思路

一. 顺序遍历O(n)

首先能想到的就是顺序遍历,数组中最小的元素即为整个旋转数组的最小元素,但算法时间复杂度为O(n)

二. 二分O(logn)

有序数组的查找大部分离不开二分。

由旋转数组的特性,因为经排序好的数组旋转得到的,所以由其特性可以知道,除了不旋转的情况(即原数组),旋转数组可以划分为两个排序的子数组,前面的子数组元素均大于后面的子数组元素,存在分界线,所以可以想到的就是利用二分查找法,实现时间复杂度为O(logn)

步骤

牢记:要求的是如果发生过旋转,第二个数组的第一个数

1. 设置两个指针low,high

low指向数组的开始位置,也就是第一个数组的开始位置
high指向数组的终止位置,也就是第二个数组的结束位置
Mid在中点

2. 比较mid与low,high位置的数组值

一直逼近第二个数组的第一个数。

mid与low,high初始数组值关系
  1. 如果中间位置mid的数大于low指向的数,则mid在第一个数组中。故让low指向mid所指向的数,low指向的依然是数组1的数
  2. 如果中间位置mid的数小于high所指向的位置,则mid在第二个数组中。故让high指向mid指向的数,high指向的依然是数组2的数
  3. 知道low和high只差1(相邻),high指针的数组值就是所求

注意考虑以下几种情况的处理:

  1. 数组元素为空的情况(返回0)
  2. 数组元素只有一个的情况(返回该元素)
  3. 数组旋转0个元素,也就是没有旋转的情况,(最后返回mid对应的值,所以初始时令mid=low,遇到该情况while条件不成立,依然返回mid对应的值)
  4. 如果mid的数既等于p1位置数,又等于p2位置的数,这时候不能确定移哪个指针,就必须采用顺序查找的方法来寻找最小数
    如,排序数组为{0,1,1,1,1},旋转数组为{1,0,1,1,1}或者{1,1,1,0,1},当为这两种情况时,mid=low=high,无法确定最小的元素在左还是在右,所以这个时候就需要采用顺序查找的方式。

代码实现

public class _11 {
    public static int min(int[] arr) {
        if (arr == null||arr.length< 1) {
            throw new RuntimeException("Invalid input.");
        }   
        if ( arr.length ==1) {
            return arr[0];
        }  
        int low = 0;// 开始处理的第一个位置
        int high = arr.length - 1;// 开始处理的最后一个位置
        int mid = low;// 设置初始值 
        // 确保low在前一个排好序的部分,high在排好序的后一个部分
        while (arr[low] >= arr[high]) {//没中while就返回mid(low)
            if (high - low == 1) {
                return arr[high];
            }
            mid = low + (high - low) / 2;
            // 如果三个数都相等,则需要进行顺序处理,从头到尾找最小的值
            if (arr[mid] == arr[low] && arr[high] == arr[mid]) {
                return minInorder(arr, low, high);
            }    
            if (arr[mid] >= arr[low]) {// 如果arr[mid]在前一个排好序的部分
                low = mid;
            }
            else if (arr[mid] <= arr[high]) {// 如果arr[mid]在后一个排好序的部分
                high = mid;
            }
        }
        return arr[mid];
    }
 
    private static int minInorder(int[] numbers, int start, int end) {//顺序处理
        int result = numbers[start];//想象一个pivot拉低整条线
        for (int i = start + 1; i <= end; i++) {
            if (result > numbers[i]) {
                result = numbers[i];
            }
        }
        return result;
    }
 
    public static void main(String[] args) {
        // 典型输入,单调升序的数组的一个旋转
        int[] array1 = {3, 4, 5, 1, 2};//1
        System.out.println(min(array1));
        // 有重复数字,并且重复的数字刚好的最小的数字
        int[] array2 = {3, 4, 5, 1, 1, 2};//1
        System.out.println(min(array2));
        // 有重复数字,但重复的数字不是第一个数字和最后一个数字
        int[] array3 = {3, 4, 5, 1, 2, 2};//1
        System.out.println(min(array3));
        // 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
        int[] array4 = {1, 0, 1, 1, 1};//0
        System.out.println(min(array4));
        // 单调升序数组,旋转0个元素,也就是单调升序数组本身
        int[] array5 = {1, 2, 3, 4, 5};//1
        System.out.println(min(array5)); 
        // 数组中只有一个数字
        int[] array6 = {2};//2
        System.out.println(min(array6));
        // 数组中数字都相同
        int[] array7 = {1, 1, 1, 1, 1, 1, 1};//1
        System.out.println(min(array7));
        // 输入NULL
        System.out.println(min(null));//java.lang.RuntimeException: Invalid input.
    }
}

输出:

1
1
1
0
1
2
1
Exception in thread "main" java.lang.RuntimeException: Invalid input.

相关文章

网友评论

      本文标题:11:旋转数组的最小数字

      本文链接:https://www.haomeiwen.com/subject/hhlhwftx.html