[LeetCode] 每日一题 81. 搜索旋转排序数组 II
题目链接
题目描述
已知存在一个按非降序排列的整数数组 nums
,数组中的值不必互不相同。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,6,7]
在下标 5
处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]
。
给你 旋转后 的数组 nums
和一个整数 target
,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums
中存在这个目标值 target
,则返回 true
,否则返回 false
。
你必须尽可能减少整个操作步骤。
示例输入
示例 1
输入:nums = [2,5,6,0,0,1,2], target = 0
输出:true
示例 2
输入:nums = [2,5,6,0,0,1,2], target = 3
输出:false
提示
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
题目数据保证
nums
在预先未知的某个下标上进行了旋转-10^4 <= target <= 10^4
解题思路
本题是 搜索旋转排序数组 的变种,数组在某个未知的下标 k
处进行了旋转,同时允许数组中包含重复元素。由于数组是部分有序的,因此可以使用二分查找,但需要额外处理重复元素的情况
核心思路:
标准二分查找框架:
计算
mid
并判断nums[mid]
是否等于target
,若相等则直接返回true
由于旋转导致数组部分有序,因此需要根据
nums[mid]
与nums[left]
及nums[right]
的关系来判断哪一部分是有序的
特殊情况处理:
当
nums[left] == nums[mid] == nums[right]
时,无法确定哪一部分是有序的,例如nums = [3,1,2,3,3,3,3]
,target = 2
在这种情况下,我们只能通过缩小搜索区间来规避无法判断的问题,即将左边界右移
left++
,将右边界左移right--
,然后继续二分查找
有序区间的判定:
若
nums[left] <= nums[mid]
,说明 左侧区间[left, mid]
是有序的:若
target
在[nums[left], nums[mid]]
之间,则搜索左侧right = mid - 1
,否则搜索右侧left = mid + 1
若
nums[left] > nums[mid]
,说明 右侧区间[mid, right]
是有序的:若
target
在[nums[mid], nums[right]]
之间,则搜索右侧left = mid + 1
,否则搜索左侧right = mid - 1
由于最坏情况下数组中所有元素都相等,可能需要遍历整个数组,因此最坏时间复杂度是 O(n),但通常情况下仍可保证 O(log n) 的效率
代码实现
class Solution {
public boolean search(int[] nums, int target) {
if (nums.length == 0) {
return false;
}
if (nums.length == 1) {
return nums[0] == target;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[left] == nums[mid] && nums[right] == nums[mid]) {
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[nums.length - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
}
复杂度分析
时间复杂度:
最坏情况下 O(n):当所有元素都相等且不等于
target
时,我们需要遍历整个数组,例如nums = [2,2,2,2,2]
,target = 3
一般情况下 O(log n):当
nums[left] != nums[mid]
或nums[mid] != nums[right]
时,二分查找仍可有效缩小搜索区间
空间复杂度:
O(1),仅使用了几个额外变量,没有额外的空间消耗
总结
本题的关键在于二分查找时如何处理重复元素,由于 nums[left] == nums[mid] == nums[right]
的情况会导致无法判断哪一部分是有序的,因此我们只能逐步缩小搜索区间,直到可以正常执行二分。通常情况下,二分查找仍能保持 O(log n) 的复杂度,但在极端情况下会退化为 O(n)。这种在部分有序数组上进行二分查找的技巧,在搜索类问题中非常常见。
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。