LeetCode 81 - 搜索旋转排序数组 II - [二分+暴力]

时间:2024-01-09 11:12:20

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [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 可能包含重复元素。
这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?

这题关键问题就是在可能有重复的数字出现,当我们在二分查找分界点时,只有严格大于和小于才能确定分界点在哪一侧,否则就只能在 $[l,r]$ 之间暴力找了。

AC代码:

bool Srch(const vector<int>& a,int st,int ed,int x)
{
int l=st, r=ed;
while(l<r)
{
int mid=(l+r)/;
if(a[mid]<x) l=mid+;
else r=mid;
}
if(a[l]!=x) return ;
else return ;
} class Solution
{
public:
bool search(const vector<int>& a,int x)
{
if(a.empty()) return ;
if(a.front()<a.back())
return Srch(a,,a.size()-,x); int l=, r=a.size()-;
while(r-l>)
{
int mid=(l+r)/;
if(a[mid]>a.front()) l=mid;
else if(a[mid]<a.back()) r=mid;
else
{
int tp;
for(int i=l;i<r;i++)
{
if(a[i]>a[i+])
{
tp=i;
break;
}
}
l=tp, r=tp+;
break;
}
} return max(Srch(a,,l,x),Srch(a,r,a.size()-,x));
}
};