Find Minimum in Rotated Sorted Array I&&II——二分查找的变形
Find Minimum in Rotated Sorted Array I
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.
You may assume no duplicate exists in the array.
思路：
当nums[left]<nums[right],说明数组没有旋转，是按升序排列的。可直接返回nums[left];
当nums[left]<nums[mid],说明left至mid这段是按升序排列的，可令left=mid+1;
当nums[left]>nums[mid],说明mid至right这段是按升序排列的，可令right=mid;
理清思路后，代码就变的异常简单了，下面的代码不是按照这个思路来的，这个思路是写II的时候才想出来的，用这个思路来写的话，非常好理解。
class Solution {
public:
int findMin(vector<int> &num) {
int len=num.size();
int Left,Right,Mid;
Left=;
Right=len-;
while(Left<=Right)
{
Mid=Left+(Right-Left)/;
if(num[len-]<num[Mid])
Left=Mid+;
else
Right=Mid-;
}
return num[Left];
}
};
Find Minimum in Rotated Sorted Array II
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.
这个思路和1差不多，关键是怎么处理重复的元素。
代码中continue那个语句是亮点。
class Solution {
public:
int findMin(vector<int>& nums) {
int len=nums.size();
int left=;
int right=len-;
int mid=;
while(left<right)
{
if(nums[left]==nums[right])
{
left++;
continue;
}
if(nums[left]<nums[right]) //这一步其实才是最大的亮点啊，解决了left=mid+1所带来的困惑，而且更加的高效
return nums[left];
mid=(left+right)/;
if(nums[mid]>=nums[left])
left=mid+;
else
right=mid;
}
return nums[left];
}
};
最新文章
- JSF标签的使用2
- 在win7下将CapsLock按键变成esc
- 作业七：团队项目——Alpha版本冲刺阶段-08
- 使用Struts 拦截namespace进行权限控制
- LeetCode Binary Tree Upside Down
- 使用Handler和Timer+Timertask实现简单的图片轮播
- VS2010与VAssistX
- Qt的十六进制的控件
- SpringMVC Hibernate+Spring+Spring MVC+Bootstrap的管理系统实现
- 【Android Developers Training】 13. 支持不同平台版本
- Developing Universal Windows Apps 开发UWA应用 问答
- python JoinableQueue在生产者消费者项目中的简单应用
- 关于Kafka日志留存策略的讨论
- 如何让微信里的html应用弹出“点击右上角分享到朋友圈”的图片
- 并行排序ShearSort ---[MPI , c++]
- Python 读取文件中unicode编码转成中文显示问题
- 案例：使用scan IP无法连接数据库
- VS2015编译OpenSSL
- Centos 安装编译codeblocks&&codelite
- Ansible自动化配置详解