首页 🍒LeetCode,🐶算法

题目

0.png

思路

可以遍历直接求。

也可以采用二分法,定义两个指针,一个指向开头,一个指向末尾。

如果中间值处于前面的递增子数组,那么中间值应该大于等于最左边的值,那么最小值应该在中间值的右边。

如果中间值处于后面的递增子数组,那么中间值应该小于等于最右边的值,那么最小值应该在中间值的左边。

确定好最小值在的区间就把那个区间再进行二分,每次进行二分查找第一个指针总是指向前面递增的子数组,第二个指针总是指向后面递增的子数组,最终第一个指针指向第一个递增子数组的最后一个元素,第二个指针指向第二个递增子数组的第一个元素,这时第二个指针指向的值即为最小值。

如果旋转了0个元素,这种情况就是numbers[0] < numbers[len(numbers)-1]直接返回第一个元素即可。

有种特殊情况即为{1, 0, 1, 1, 1}和{1, 1, 1, 0, 1}。
这两个数组的第一个指针 == 第二个指针 == 中间值,所以无法判断中间值属于哪边的递增子数组,这种情况只能进行从头遍历查找。

func minArray(numbers []int) int {
    if len(numbers) == 1 {
        return numbers[0]
    }
    if numbers[0] < numbers[len(numbers)-1] {
        return numbers[0]
    }
    return find(numbers, 0, len(numbers)-1)
}

func find(nums []int, l, r int) int {
    if l+1 == r {
        return nums[r]
    }
    mid := (l + r) / 2
        // 从头遍历查找
    if nums[l] == nums[r] && nums[l] == nums[mid] {
        return psFind(nums)
    }
    if nums[l] <= nums[mid] {
        return find(nums, mid, r)
    } else {
        return find(nums, l, mid)
    }
}

func psFind(nums []int) int {
    res := math.MaxInt32
    for _, v := range nums {
        if res > v {
            res = v
        }
    }
    return res
}



文章评论