剑指Offer - 面试题11. 旋转数组的最小数字(二分查找)
发布日期:2021-07-01 03:20:12
浏览次数:2
分类:技术文章
本文共 859 字,大约阅读时间需要 2 分钟。
1. 题目
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2]
为 [1,2,3,4,5]
的一个旋转,该数组的最小值为1。
示例 1:输入:[3,4,5,1,2]输出:1示例 2:输入:[2,2,2,0,1]输出:0
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。2. 解题
相同题目:
- mid 与 left 比较不能确定选择那一侧继续查找,例如:[3, 4, 5, 1, 2] 与 [1, 2, 3, 4, 5] ,mid 位置的值 都比 left 大,无法确定哪边
- 用 mid 与 right 比较
class Solution { public: int minArray(vector & num) { if(num.size()==1 || num[0] < num.back()) return num[0]; int l = 0, r = num.size()-1, mid; while(l <= r) { mid = l +((r-l)>>1); //最小的肯定不在左侧 if(num[mid] > num[r]) l = mid+1; //mid右侧的肯定不是,mid可能是 else if(num[mid] < num[r]) r = mid; else//相等,r可以忽略,-1 r--; } return num[l];//上面l==r时,r--,所以返回l }};
转载地址:https://michael.blog.csdn.net/article/details/104295164 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年05月01日 09时52分36秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java并发编程(一)----线程基础知识
2019-05-03
java并发编程(二)----创建并运行java线程
2019-05-03
Asp.Net MVC4入门指南(1): 入门介绍
2019-05-03
分享ISTQB培训体验
2019-05-03
Asp.Net MVC4入门指南(3):添加一个视图
2019-05-03
我看TechEd 2012之技术热点
2019-05-03
QCon所见和所得:杭州QCon热门技术话题分享
2019-05-03
古城钟楼微博:葡萄城程序员演练技术的产物
2019-05-03
Asp.Net MVC4入门指南(4):添加一个模型
2019-05-03
Asp.Net MVC4入门指南(5):从控制器访问数据模型
2019-05-03
我看TechEd 2012之App时代降临
2019-05-03
WinRT开发语言的功能和效率
2019-05-03
Asp.Net MVC4入门指南(6):验证编辑方法和编辑视图
2019-05-03
Asp.Net MVC4入门指南(8):给数据模型添加校验器
2019-05-03
Asp.Net MVC4入门指南(7):给电影表和模型添加新字段
2019-05-03
Asp.Net MVC4入门指南(9):查询详细信息和删除记录
2019-05-03
Spread Studio中文支持图解
2019-05-03
2013 北京 QCon热点分享
2019-05-03