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

简介: 剑指offer_数组---旋转数组的最小数字

题目描述

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

解题思路

1,使用Arrays.sort

2,暴力遍历法

3,二分查找

代码实现

package 数组;
import java.util.Arrays;
public class MinNumberInRotateArray {
    public static void main(String[] args) {
        int[] array = { 1,1,1,0,1 };
        System.out.println(new MinNumberInRotateArray()
                .minNumberInRotateArraySuperFind(array));
    }
    // =========================================================非技巧解法利用Arrays的sort函数,直接排序O(nlogn)
    public int minNumberInRotateArray(int[] array) {
        if(array==null||array.length<1){
            throw new RuntimeException("数组不合法");
        }
        Arrays.sort(array);
        return array[0];
    }
    // ==========================================================技巧解法,暴力遍历法O(n)
    public int minNumberInRotateArraySuper(int[] array) {
        if(array==null||array.length<1){
            throw new RuntimeException("数组不合法");
        }
        int i = 0;
        for (; i < array.length; i++) {
            if (array[i] > array[i + 1]) {
                break;
            }
        }
        return array[i + 1];
    }
    // ==========================================================技巧解法,二分查找法O(logn)
    public int minNumberInRotateArraySuperFind(int[] array) {   
        if(array==null||array.length<1){
            throw new RuntimeException("数组不合法");
        }
        int low = 0;
        int high = array.length-1;
        int middle =0;
        while(low<high){
            middle = (high+low)/2;
            if(array[middle]>array[high]){    //middle在左边递增区间
                low = middle+1;            //最小值在middle右边
            }else if(array[middle]==array[high]){    //1,1,1,0,1这样没有办法只能顺序遍历
                Arrays.sort(array);
                return array[0];
            }
            else{
                high = middle;           //middle在右边递增区间,最小值在middle或者middle左边
            }
        }
        return array[low];
    }
}


相关文章
|
6月前
|
Java
【剑指offer】-旋转数组的最小数字-06/67
【剑指offer】-旋转数组的最小数字-06/67
|
1月前
(剑指Offer)04、二维数组中的查找11、旋转数组的最小数字50、第一个只出现一次的字符(2021.12.02)
(剑指Offer)04、二维数组中的查找11、旋转数组的最小数字50、第一个只出现一次的字符(2021.12.02)
30 1
|
6月前
每日一题——旋转数组的最小数字(II)
每日一题——旋转数组的最小数字(II)
|
6月前
|
Java
每日一题《剑指offer》数组篇之旋转数组的最小数字
每日一题《剑指offer》数组篇之旋转数组的最小数字
39 0
每日一题《剑指offer》数组篇之旋转数组的最小数字
|
6月前
牛客网-旋转数组的最小数字
牛客网-旋转数组的最小数字
35 0
剑指offer-10.旋转数组最小的数字
剑指offer-10.旋转数组最小的数字
58 0
剑指offer_数组---把数组排成最小的数
剑指offer_数组---把数组排成最小的数
47 0
剑指offer_数组---连续子数组的最大和
剑指offer_数组---连续子数组的最大和
46 0
剑指offer_数组---最小的K个数
剑指offer_数组---最小的K个数
48 0
|
算法
剑指offer 10. 旋转数组的最小数字
剑指offer 10. 旋转数组的最小数字
55 0