欢迎访问LeetCode题解合集
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [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
进阶:
- 这是 搜索旋转排序数组 的延伸题目,本题中的
nums
可能包含重复元素。 - 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?
题解:
参考 搜索旋转排序数组 一题,这题增加了一个条件:可以有重复值,这个条件有点麻烦。。。
还是用二分来搞定。
注意:二分不一定必须要有单调性,二分的本质是寻找某种性质的分界点。只要找到某种性质,可以确定目标在区间的前半部分还是后半部分,就可以用二分找到这个分界点。
为了便于分析,将数组中的元素画在二维坐标系中,横轴代表下标,纵轴代表值。
水平的实线表示相同的元素。可以发现,除了黑色水平那段,其余部分均满足二分性质:竖直的虚线左边的元素均满足$arr[i]>=arr[0]$,而虚线右边(除了黑色部分)元素均满足$arr[i]<arr[0]$。
首先,我们需要把黑色的水平段删除,至于为什么删除呢?考虑一种情况:$arr[mid] == a[0]$,这种情况下,根本不知道往哪边走,所以只能删除。
还需要处理数组未旋转的情况,当删除黑色水平段后,若剩下的最后一个元素大于等于arr[0],说明数组完全单调。
最坏情况:元素均相等情况下的时间复杂度为$O(n)$。
法一:
两次二分。参考 在有序旋转数组中找到最小值 一题,如果我们可以找到分界点,就可以确定 target
在左右哪个区间,然后直接在该区间上进行二分查找即可。
把复杂问题分解成简单的子问题 思想很重要。
class Solution {
public:
bool search(vector<int>& nums, int target) {
int n = nums.size();
if ( !n ) return false;
n -= 1;
while ( n && nums[n] == nums[0] ) --n;
if ( !n ) return nums[0] == target;
if ( nums[0] < nums[n] ) {
if ( target < nums[0] || target > nums[n] )
return false;
}
int l = 0, r = n, m;
if ( nums[0] > nums[n] ) {
while ( l < r ) {
m = ( l + r ) >> 1;
if ( nums[m] == target ) return true;
if ( nums[m] >= nums[0] ) l = m + 1;
else r = m;
}
if ( target <= nums[n] ) r = n;
else l = 0, --r;
}
while ( l < r ) {
m = ( l + r ) >> 1;
if ( nums[m] == target ) return true;
if ( nums[m] > target ) r = m;
else l = m + 1;
}
return nums[r] == target;
}
};
/*
时间:4ms,击败:94.08%
内存:13.6MB,击败:29.95%
*/
法二:
在二分过程中,通过一些条件判断 target
在哪个区间也行:
- 若 $nums[mid] >= nums[0]$,说明
mid
在左边区间:
1.若 $target >= nums[l] \quad and \quad target <= nums[mid]$,说明此时要在区间[l,mid]
查找,r = mid
;
2.若 $target < nums[l]$,说明target
在右边区间,l = mid + 1
;
3.若 $target > nums[mid]$,说明target
在mid
右边,l = mid + 1
; - 若 $nums[mid] < nums[0]$,说明
target
在右边区间:
1.若 $target <= nums[mid]$,说明target
在mid
左边,r = mid
;
2.若 $target > nums[n]$,说明target
在左边区间,r = mid
;
3.否则的话,说明target
在mid
右边,l = mid + 1
;
class Solution {
public:
bool search(vector<int>& nums, int target) {
int n = nums.size();
if ( !n ) return false;
n -= 1;
while ( n && nums[n] == nums[0] ) --n;
if ( !n ) return nums[0] == target;
if ( nums[0] < nums[n] ) {
if ( target < nums[0] || target > nums[n] )
return false;
}
int l = 0, r = n, m;
while ( l < r ) {
m = ( l + r ) >> 1;
if ( nums[m] == target ) return true;
if ( nums[m] >= nums[0] ) {
if ( nums[0] <= target && target <= nums[m] ) r = m;
else l = m + 1;
} else {
if ( target <= nums[m] || target > nums[n] ) r = m;
else l = m + 1;
}
}
return nums[r] == target;
}
};
/*
时间:4ms,击败:94.08%
内存:13.6MB,击败:30.23%
*/
法三:
直接扫描一遍 nums
。。。
class Solution {
public:
bool search(vector<int>& nums, int target) {
for ( auto& it : nums )
if ( it == target ) return true;
return false;
}
};
/*
时间:4ms,击败:94.08%
内存:13.6MB,击败:22.29%
*/
三种方法内存消耗简直离谱。。。