LeetCode 153. 寻找旋转排序数组中的最小值
题目描述
思路分析
这个问题可以使用二分查找来解决。由于数组是旋转排序的，我们可以利用这一特性来缩小搜索范围。
- 初始化指针：设置两个指针
left和right，分别指向数组的开始和结束。- 二分查找：
- 计算中间索引
mid。- 如果
nums[mid]大于nums[right]，说明最小值在mid右侧，因此将left移动到mid + 1。- 如果
nums[mid]小于nums[right]，说明最小值在mid左侧或mid本身，因此将right移动到mid。- 如果
nums[mid]等于nums[right]，则无法确定最小值的位置，可以将right减 1，缩小范围。- 结束条件：当
left等于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
} else {
// 当中间元素等于右侧元素时，无法确定最小值的位置，缩小搜索范围
right--
}
}
return nums[left]
}
- 时间复杂度：O (log n)，因为我们使用了二分查找。
- 空间复杂度：O (1)，只使用了常数级别的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！