LeetCode Search in Rotated Sorted Array II -- 有重复的旋转序列搜索
2024-08-29 09:04:04
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
class Solution {
public:
bool search(int A[], int n, int target) {
int l=,r=n-;
while(l<=r){
if(target==A[l]||target==A[r])
return true;
int m =(l+r)/;
if(target==A[m])
return true;
if(A[l]<A[m]){
if(target<A[m]&&target>A[l])
r=m-;
else
l=m+;
}else if(A[l]>A[m]){
if(target>A[m]&&target<A[r])
l=m+;
else
r=m-;
}else
l++;
}
return false;
}
};
这道题是二分查找Search Insert Position的变体,思路在Search in Rotated Sorted Array中介绍过了,不了解的朋友可以先看看那道题哈。和Search in Rotated Sorted Array唯一的区别是这道题目中元素会有重复的情况出现。不过正是因为这个条件的出现,出现了比较复杂的case,甚至影响到了算法的时间复杂度。原来我们是依靠中间和边缘元素的大小关系,来判断哪一半是不受rotate影响,仍然有序的。而现在因为重复的出现,如果我们遇到中间和边缘相等的情况,我们就丢失了哪边有序的信息,因为哪边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3},那么旋转之后有可能是{3,3,3,3,3,1,2},或者{3,1,2,3,3,3,3},这样的我们判断左边缘和中心的时候都是3,如果我们要寻找1或者2,我们并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步,直到边缘和中间不在相等或者相遇,这就导致了会有不能切去一半的可能。所以最坏情况(比如全部都是一个元素,或者只有一个元素不同于其他元素,而他就在最后一个)就会出现每次移动一步,总共是n步,算法的时间复杂度变成O(n)。代码如下:
最新文章
- Django admin美化插件suit应用[原创]
- wifi,网关相关标识的获取
- 深入理解gradle编译-Android基础篇
- [Intellij] 编译报错 javacTask
- iOS开发— Socket编程
- Struts之ForwardAction
- yii2源码学习笔记(九)
- HDU 1695 GCD(欧拉函数+容斥原理)
- new Handler().postDelayed() 延迟intent跳转
- 日期和时间特效-查看";今天是否为节假日";
- jtag、在线仿真器
- Myeclipse版本引发的css样式问题:头部自动生成一行代码导致样式引入不成功
- 【UER #1】DZY Loves Graph(待卡常数)
- Windows 7用U盘安装CentOS 7
- psycopg事务
- POJ-2081 Terrible Sets(暴力,单调栈)
- 通过sizeof获得数组长度的方法
- pywin32记录备忘
- TFS WorkItem Permission Setting
- js 面向对象 定时器 046
热门文章
- JVM(8):JVM知识点总览-高级Java工程师面试必备
- Groovy安装
- 修改Linux内核参数 减少TIME-WAIT
- C#添加编译时间
- 编译linux kernel及制作initrd ( by quqi99 )
- HDU 2065 ";红色病毒";问题 ——快速幂 生成函数
- 使用非对称算法RSA实现加解密和使用签名算法SHA1WithRSA、MD5withRSA生成签名以及验签
- 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest A E F G H I K M
- Heritrix3.0.0启动介绍
- linux根文件系统制作之busybox编译和系统构建【转】