LeetCode 154. 寻找旋转排序数组中的最小值 II
题目描述
思路分析
在这个问题中，我们可以使用二分查找的方法来寻找最小值。由于数组是旋转排序的，我们可以利用这一特性来缩小查找范围。
- 初始化指针：设置两个指针
left和right，分别指向数组的开始和结束。- 循环查找：在
left < right的情况下，进行以下操作。
- 计算中间索引
mid。- 如果
nums[mid]大于nums[right]，说明最小值在右半部分，因此将left移动到mid + 1。- 如果
nums[mid]小于nums[right]，说明最小值在左半部分或就是mid，因此将right移动到mid。- 如果
nums[mid]等于nums[right]，我们无法确定最小值的位置，因此将right减一。- 返回结果：当
left等于right时，返回nums[left]或nums[right]，即为最小值。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func findMin(nums []int) int {
left, right := 0, len(nums)-1
for left < right {
mid := left + (right-left)/2
if nums[mid] > nums[right] {
left = mid + 1 // 最小值在右侧
} else if nums[mid] < nums[right] {
right = mid // 最小值在左侧或是 mid
} else {
right-- // 处理重复元素
}
}
return nums[left] // 或者 nums[right]
}
- 时间复杂度：O (log n) 最坏情况下为 O (n)，当数组中有很多重复元素时。
- 空间复杂度：O (1)，只使用了常数级别的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！