怎么将自己做的网站发到网上去,腾讯云手动搭建wordpress个人站点,最佳网站制作模板,网站如何开发触屏版这是索引二分的第七篇算法#xff0c;力扣链接 已知一个长度为 n 的数组#xff0c;预先按照升序排列#xff0c;经由 1 到 n 次 旋转 后#xff0c;得到输入数组。例如#xff0c;原数组 nums [0,1,4,4,5,6,7] 在变化后可能得到#xff1a; 若旋转 4 次#xff0c;则可…这是索引二分的第七篇算法力扣链接 已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,4,4,5,6,7] 在变化后可能得到 若旋转 4 次则可以得到 [4,5,6,7,0,1,4]若旋转 7 次则可以得到 [0,1,4,4,5,6,7] 注意数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 给你一个可能存在 重复 元素值的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须尽可能减少整个过程的操作步骤。 示例 1 输入nums [1,3,5]
输出1示例 2 输入nums [2,2,2,0,1]
输出0 和上一篇算法的本质区别是这个多了个可以能存在重复的条件此外这里不限制log n了。
老规矩先求解暴力从左到右遍历找到最小值当当前值小于左边的值不包括等于的时候证明位于右区间最低谷返回即可。
func findMin(nums []int) int {for i : 1; i len(nums); i {if nums[i] nums[i-1] {return nums[i]}}return nums[0]
}
接着我们尝试正规的解法例如类似于上次的二分法
当前的数组可能处于一个断崖式递增的双区间中我们可以分类讨论。
当mid大于nums[len(nums)-1]证明mid位于左区间最小值应该位于右区间我们要将左指针右移。
当mid小于nums[len(nums)-1]证明mid位于右区间尽量将右指针左移。
此外这里有一个条件是存在相等的场景当nums[0]、nums[len(nums)-1]、nums[mid]相等的时候我们是无法区分左右区间的我们将左右指针向中间靠拢即可。这种情况会导致我们比较的边界可能会不再是nums[0]或者nums[len(nums)-1]了而是nums[l]和nums[r]。
func findMin(nums []int) int {l, r : 0, len(nums)-1for l r {mid : l (r-l)/2if nums[l] nums[r] nums[mid] nums[r] {lr--} else if nums[mid] nums[r] {if mid 0 nums[mid] nums[mid-1] {return nums[mid]}r mid - 1} else {l mid 1}}return nums[l]
}
尝试左开右闭的解题思路
这也是一种分情况讨论。
当mid小于nums[len(nums)-1]证明位于右区间正常右指针左移取值。
当mid大于nums[len(nums)-1]证明位于左区间尽量让左指针靠右。
当mid等于nums[len(nums)-1]缩小范围在判断。
func findMin(nums []int) int {l, r : 0, len(nums)-1for l r {mid : l (r-l)/2if nums[mid] nums[r] {r mid} else if nums[mid] nums[r] {l mid 1} else {r--}}return nums[l]
}
