LeetCode 81. 搜索旋转排序数组 II
题目描述
思路分析
由于数组是旋转排序的，并且可能包含重复元素，我们可以使用变种的二分查找来解决这个问题。基本思路如下：
- 初始化指针：设置两个指针
left和right，分别指向数组的开始和结束。- 二分查找：
计算中间索引
mid。检查
nums[mid]是否等于目标值target，如果相等则返回true。如果
nums[left]、nums[mid]和nums[right]都相等，则无法确定哪一部分是有序的，因此可以通过left++和right--来缩小范围。如果左半部分有序（
nums[left] <= nums[mid]）：检查目标值是否在左半部分，如果在，则将
right移动到mid - 1，否则将left移动到mid + 1。如果右半部分有序（
nums[mid] <= nums[right]）：检查目标值是否在右半部分，如果在，则将
left移动到mid + 1，否则将right移动到mid - 1。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func search(nums []int, target int) bool {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return true
}
// 处理重复元素
if nums[left] == nums[mid] && nums[mid] == nums[right] {
left++
right--
} else if nums[left] <= nums[mid] { // 左半部分有序
if nums[left] <= target && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else { // 右半部分有序
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return false
}
- 时间复杂度：最坏情况下为 O (n)，因为在处理重复元素时，可能会导致每次只移动一个指针。
- 空间复杂度：O (1)，只使用了常数级别的额外空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func search(nums []int, target int) bool {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return true
}
if nums[mid] > nums[right] {
if target >= nums[left] && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else if nums[mid] < nums[right] {
if target > nums[mid] && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
} else {
right--
}
}
return false
}
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！