LeetCode 154. 寻找旋转排序数组中的最小值 II
题目描述
思路分析
在这个问题中，我们可以使用二分查找的方法来寻找最小值。由于数组是旋转排序的，我们可以利用这一特性来缩小查找范围。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
} else { // nums[mid] == nums[right] 时不能确定，缩小右边界
right--
}
}
return nums[left]
}
- 时间复杂度：O (log n) 最坏情况下为 O (n)，当数组中有很多重复元素时。
- 空间复杂度：O (1)，只使用了常数级别的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！