注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex81 Search in Rotated Sorted Array II  

2015-05-24 21:11:57|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个和ex33极为相似,就是放宽了条件,可能array里面有重复的数组

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.

我表示我只是把我ex33的改动了一点儿如下,其实就是一个边界判断的问题。平局复杂度还是比线性要好一些,只有当每次循环的时候落到最后一个分支的时候才是线性的。

/*
* 再加了重复元素之后,都落在最后一个区间也就是left++那个区间
* 但是平局起来还是比线性查找要好
*/
class Solution {
public:
bool search(vector<int>& nums, int target) {
int numsSize = nums.size();
int left, right, mid;
left = 0;
right = numsSize - 1;
while (left <= right)
{
mid = left + (right - left) / 2;
if (target == nums[mid])
return true;
if (nums[left]<nums[mid])
{
// 说明落在第一个上升区间
if (nums[left] <= target&&target < nums[mid])
{
//在left 和mid-1的区间搜索
right = mid - 1;
}
else
{
left = mid + 1;
}
}
else if (nums[left]>nums[mid])
{
//说明落在第二个上升区间
if (nums[mid]<target&&target <= nums[right])
{
//在left 和mid-1的区间搜索
left = mid + 1;
}
else
{
right = mid - 1;
}

}
else
{
left = left + 1; //只需要把我的上一个程序上left值直接改为
//left++ 就可以了 //原来是left = mid +1;
}
}

return false;
}
};



  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017