题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组[0,0,1,2,2,5,6]
可能变为[2,5,6,0,0,1,2]
)。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回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
说明
-
这是 Search in Rotated Sorted Array 的延伸题目,本题中的
nums
可能包含重复元素。 -
这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?
算法1
(两次二分) $O(n)$
与 LeetCode 33. Search in Rotated Sorted Array 一样,这道题目可以只用一次二分搜索来直接做,不过这样需要考虑的情况会比较多,很麻烦。所以这里我们采用分解的思想,原问题不好做的时候我们尝试将问题分解成简单的子问题。
第一步我们可以用二分来找到旋转点,换句话说就是找到旋转数组当中的最小值,这就和 LeetCode 154. Find Minimum in Rotated Sorted Array II 一模一样了(这里想吐槽一下第154题是Hard
难度结果本题居然只是Medium
)。
找到最小值后我们判断一下target
属于哪一部分,之后直接二分搜索就可以了。
时间复杂度
找到最小值最差情况下即数组元素全部相同的情况下需要$O(n)$的时间,因此总复杂度为$O(n)$。
C++ 代码
class Solution {
public:
bool search(vector<int>& nums, int target) {
if (nums.empty()) return false;
int l = 0;
int t = nums.size() - 1;
while (t > 0 && nums[t] == nums[0]) t -- ;
int r = t;
// 找到最小值
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] <= nums[t]) r = mid;
else l = mid + 1;
}
if (target <= nums[t]) r = t; // 答案在右半边
else l = 0, r -- ; // 答案在左半边
// 搜索答案,直接套模板
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return nums[l] == target;
}
};
算法2
(一次二分) $O(n)$
和 LeetCode 33. Search in Rotated Sorted Array 一样,我们观察数组具有怎样的性质。不难看出当nums[mid]
大于或者小于nums[r]
的时候我们依然可以判断出中点是在左半边还是右半边,不同的地方在于当nums[mid]
等于nums[r]
的时候我们不能确定中点的位置,但此时依然可以缩小区间,这里我们直接让右边界r
减一就好了。原因在于将nums[r]
排除出去依然可以保证答案仍在区间内因为我们有mid < r && nums[mid] == nums[r]
。
C++ 代码
class Solution {
public:
bool search(vector<int>& nums, int target) {
if (nums.empty()) return false;
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < nums[r]) {
if (target > nums[mid] && target <= nums[r]) l = mid + 1;
else r = mid;
} else if (nums[mid] > nums[r]) {
if (target <= nums[mid] && target >= nums[l]) r = mid;
else l = mid + 1;
}
else r -- ;
}
return nums[l] == target;
}
};
想问下这份代码为啥过不了,第一个二分求小于等于nums[0]的最小值,求大佬解答
第一个二分不能找到小于等于
nums[0]
的最小值,因为当nums[mid] > nums[0]
的时候,最小值可能在mid
的左边(当数组未被旋转的时候),也可能在mid
的右边(当数组被旋转的时候),所以我们不能用左边界nums[0]
来二分,而应该用右边界nums[R]
来二分。可以参考 https://www.acwing.com/solution/LeetCode/content/6386/ 里算法二的思路。可不可以理解为如果是小于等于num[0]不能满足二段性,小于等于nums[0]的元素既可以在分段点左边又可以在分段点右边(数组旋转后)
例如: 4 5 6 1 2 3, 如果是小于等于4则此数组不能被分为两段,如果是大于等于4此数组能被分为两段
嗯这样理解也是可以的
嗯嗯,谢谢
方法一预处理这一步很妙,处理完直接正常搞就完事了