9. 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路

该题目考察的是使用二分法开实现查找，
中间位置：mid = start + (end - start)/2

需要考虑三种情况：

1.中间位数值大于末尾数值（ array[mid] > array[end]）:
出现这种情况的array类似{3,4,5,6,1,2}，现在最小数字一定在mid的右边。
则:start = mid + 1

  1. 中间位数值等于末尾数值（array[mid] == array[high]):
    出现这种情况的array类似{1,0,1,1,1} 或者{1,1,1,0,1}，现在最小数值不好确定是在mid左边或者右边，则将右侧末尾位置逐渐缩小，继续检测
    high = high - 1
  2. 中间位数值小于末尾位数值（array[mid] < array[high]）:
    出现这种情况可以确定最小数字一定在mid的左边（或者就是mid位置的值），则：
    high = mid

代码实现

java 代码

    /**
     * 查找旋转数组中的最小值
     * @param array 旋转数组
     * @return 数组中的最小值
     */
    private int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        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--;
            }else {
                end = mid;
            }
        }
        return array[start];
    }

    public static void main(String[] args){
        int[] arr = {3,4,5,6,1,2};
        System.out.println(minNumberInRotateArray(arr));
    }

Kotlin 代码

     /**
     * 查找旋转数组中的最小值
     * @param array 旋转数组
     * @return 数组中的最小值
     */
    private fun minNumberInRotateArray(array: IntArray?): Int {
        if (array == null || array.isEmpty()) {
            return -1
        }
        if (array.size == 1) {
            return array[0]
        }
        var start = 0
        var end = array.size - 1
        while (start < end) {
            val mid = start + (end - start) / 2
            when {
                array[mid] > array[end] -> {
                    start = mid + 1
                }
                array[mid] == array[end] -> {
                    end--
                }
                else -> {
                    end = mid
                }
            }
        }
        return array[start]
    }

    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        val arr = intArrayOf(3,4,5,6,1,2)
        println(minNumberInRotateArray(arr))
    }

引用声明

该题目引用自
牛客网