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

HT·生活

123

 
 
 

日志

 
 

ex154 Find Minimum in Rotated Sorted Array II  

2015-05-26 22:42:02|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
和ex153相比这里就多了一个重复元素的要求。

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

我的代码改动也很小,就是多了一个nums[mid]==nums[high]的判定。
改变后的

int findMin1(int* nums, int numsSize)
{
if (numsSize <= 0)
return 0;
int i, j;
int min = nums[0];
int low = 0, high = numsSize - 1, mid;
//这里选择的是闭区间
while (low<high) //原来是这个语句//while (nums[low]>nums[high])
{
if (nums[low] < nums[high])
return nums[low]; //加了一条判定
mid = low + (high - low) / 2;
if (nums[mid]>nums[high])
{
low = mid + 1; //搜索 最小值不可能是mid下标的,
}
else if (nums[mid]<nums[high])
{
high = mid;
}
else
{
low++; //如果nums[mid]和nums[high]一样的话
//就不能做二分了,但是肯定最小值不是在low这边,只能在high那边
}
}
return nums[low]; //退出的时候肯定nums[low]<=mid[high]
}


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

历史上的今天

评论

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

页脚

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