63 搜索旋转排序数组II
2024-08-29 04:24:06
原题网址：https://www.lintcode.com/problem/search-in-rotated-sorted-array-ii/description
描述
跟进“搜索旋转排序数组”，假如有重复元素又将如何？
是否会影响运行时间复杂度？
如何影响？
为何会影响？
写出一个函数判断给定的目标值是否出现在数组中。
您在真实的面试中是否遇到过这个题？ 是
样例
给出[3,4,4,5,7,0,1,2]和target=4，返回 true
标签
二分法
排序数组
数组
思路：方法与搜索排序数组类似，只是多了一个重复判断，如果 left 处元素与 mid 处元素相同，left++；
left 处元素与 mid 处元素相同不好判断mid的左侧是单调区间还是右侧是，因为有两种情况：left~mid 部分的元素相同，如【9,9,9,9,9,5,6,7,8,9】，这时可以直接跳过这部分去判断 mid+1 ，即 left++；或者类似于【9,5,6,7,8,9,9,9,9,9】。
元素重复会影响时间复杂度，因为重复是无法折半查找，而是以距离1步进，时间复杂度会变大。
AC代码：
class Solution {
public:
/**
* @param A: an integer ratated sorted array and duplicates are allowed
* @param target: An integer
* @return: a boolean
*/
bool search(vector<int> &A, int target) {
// write your code here
if (A.empty())
{
return false;
}
int size=A.size();
int left=,right=size-,mid;
while(left<=right)
{
mid=(left+right)/;
if (A[mid]==target)
{
return true;
}
if (A[mid]>A[left])
{
if (A[left]<=target&&target<A[mid])
{
right=mid-;
}
else
{
left=mid+;
}
}
else if (A[mid]<A[left])
if (target>A[mid]&&target<=A[right])
{
left=mid+;
}
else
{
right=mid-;
}
}
else//无法判断 mid 左侧还是右侧是单调区间，直接left++;
{
left++;
}
}
return false;
}
};
参考：
https://www.cnblogs.com/libaoquan/p/7116860.html
Mark一个资源：算法总结—二分搜索与旋转排序数组
最新文章
- 【整理】C#文件操作大全(SamWang)<转>
- Git学习笔记（二）
- Java基础试题
- MSSQL Server Transaction 数据库事务回滚的用法
- 二、CSS 基本介绍
- Kinect For Windows V2开发日志四：使用OpenCV显示深度图像
- javaScript创建无边框iframe兼容ie
- java的深复制与浅复制
- 把list集合的内容写入到Xml中，通过XmlDocument方式写入Xml文件中
- HKE和他的小朋友（矩乘快速幂）
- 理解Lambda表达式和闭包
- Python实现 -- 冒泡排序、选择排序、插入排序
- httpclient初步封装
- spring创建单例bean
- 关于linq的几个小例子
- js 取值 getElementsByTagName,getElementsByName
- 关于java项目中的.project文件：
- Linux命令参数处理 shell脚本函数getopts
- EndNote登陆Web账号时解决不断询问用户名密码
- C#使用Command将dataGrideView表格内数据与数据库交互