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
2. 中间位数值等于末尾数值(array[mid] == array[high]):
出现这种情况的array类似{1,0,1,1,1} 或者{1,1,1,0,1},现在最小数值不好确定是在mid左边或者右边,则将右侧末尾位置逐渐缩小,继续检测
high = high - 1
3. 中间位数值小于末尾位数值(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))
}

引用声明

该题目引用自
牛客网