2023-8-24

8-24

数组

题号剑指 Offer 11. 旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

解法一：二分法

function minArray(numbers: number[]): number {
    let i = 0
    let j = numbers.length-1
    
    while(i <j){
        let m = Math.floor((i+j)/2)
        if(numbers[m]>numbers[j])i = m+1
        else if(numbers[m]<numbers[j])j = m
        else{
            let x = i
            for(let k = i+1;k<j;k++){
                if(numbers[k]<numbers[x])x= k
            }
            return numbers[x]
        }
    }
    return numbers[i]
    
};

题解：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solutions/102826/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/

解法二：暴力解法

function minArray(numbers: number[]): number {
    for(let i =0;i<numbers.length-1;i++){
        if(numbers[i]>numbers[i+1])return numbers[i+1]
        
    }
    return numbers[0]
};