旋转数组的最小数字

题目描述

示例

代码

代码1 暴力解法，全部比较一个遍，时间复杂度O(n)

/*
暴力解法，比较全部，取最小值
*/
function minNumberInRotateArray(rotateArray)
{
    let min = rotateArray[0]
    
    for(let i =0; i< rotateArray.length; i++){
        if(rotateArray[i] < min){
            min = rotateArray[i]
        }
    }
    
    return min
}

时间复杂度O(n)：n为数组长度

空间复杂度O(1)

代码2 变化的二分查找，逐步缩小区间，找到临界处

/*
变化的二分
*/
function minNumberInRotateArray(rotateArray)
{
    let low = 0
    let high = rotateArray.length - 1
    
    // 因为本身是一个递增的数组
    // 但是因为旋转了，所以数组分为了两半，左边的一半会比右边的一半大
    // 1.所以，当使用二分查找时，如果 low < mid ，说明左边的一半还是递增的
    //     因为左边的这一半都比右边的大，所以现在的mid还处于大区间的一边，
    //     所以，low = mid + 1 ，让区间往右缩，去找那个小值
    // 2. 而low不再小于mid的时候，应该是mid已经到了小区间。此时的mid很有可能会直接压在最小值的上面
    //     所以，让high = mid， 向左缩小区间，找这个最小值
    // 3. 如果判断不出来了，很有可能现在就剩两个数了，就是两个区间相邻的那两个数
    //     所以此时的low和mid是在一个地方的，high在low的右边一位
    //    此时只需要让low往右移动一位即是最小值了，也正好跳出循环，返回结果
    // 4. 另一种特殊情况，1 1 0 1 1 1，有相等的值，说明也快到大区间和小区间的临界处了
    //     也只需把 low 右移一位 继续循环着找
    // 总结，就是当判断不出来的时候，让low右移一位，继续循环判断，一位一位的缩小区间
    while(low < high){
        
        
        // 子数组是非递减的数组， 10111
        if(rotateArray[low] < rotateArray[high]){
            return rotateArray[low]
        }
        
        let mid = Math.floor( (low + high)/2 )
        
        if(rotateArray[mid] > rotateArray[low]){
            low = mid + 1
        }else if(rotateArray[mid] < rotateArray[high]){
            high = mid
        } else {
            // 如果判断不出来，就可能是特殊情况了，有想等的值，或者直接是大区间和小区间的临界处
            // 让low右移一位，进入下一次判断
            low++
        }
    }
    
    return rotateArray[low]
    
}

时间复杂度O(logn)

空间复杂度O(1)

题目来源

JZ11 旋转数组的最小数字

参考题解