剑指 Offer 11. 旋转数组的最小数字
剑指 Offer 11. 旋转数组的最小数字
SakuraTears
发布于 2022-01-13 15:10:34
发布于 2022-01-13 15:10:34
题目
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
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022年01月05日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录