Leetcode33.Search in Rotated Sorted Array搜索旋转排序数组
2024-10-08 02:06:13
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
class Solution {
public:
int search(vector<int>& nums, int target)
{
int len = nums.size();
int low = 0;
int high = len - 1;
//找到正常排序的起点,即原数组的第一个元素
while(low < high)
{
int mid = (low + high) / 2;
//如果用<来判断,那么对应下面会改为high = mid - 1,在正常的排序下high最后会<0
if(nums[mid] > nums[high])
{
low = mid + 1;
}
else
{
high--;
}
}
int rotate = low;
low = 0;
high = len - 1;
while(low <= high)
{
int mid = (low + high) / 2;
//将mid值进行旋转
int realMid = (mid + rotate) % len;
if(nums[realMid] == target)
return realMid;
else if(nums[realMid] > target)
{
//必须在原mid值上进行操作
high = mid -1;
}
else
{
low = mid + 1;
}
}
return -1;
}
};
最新文章
- ReportViewer内存泄漏问题解决方案[上]
- JavaScript学习笔记-基础语法、类型、变量
- MySQL的高级查询
- PostgreSQL下,对汉字按拼音排序
- Dealloc 在哪个线程执行
- ios 免书籍入门站点
- POJ#2065. SETI
- poj1849
- axf、elf文件转换成bin、hex脚本工具
- .ctor,.cctor 以及 对象的构造过程
- 朗科U903 低级格式化后,量产错误:read onlypage (控制器芯片群联2251-03)的解决方案
- linux thread 互斥锁
- http://msh.baidu.com/UTWpR6wY4722
- C# 去除文件和文件夹的只读属性
- Linux kernel 4.9及以上开启TCP BBR拥塞算法
- ITU-T G.1080 IPTV的体验质量(QoE)要求 (Quality of experience requirements for IPTV services)
- [Redis]Redis的设计与实现-链表/字典/跳跃表
- 微信小程序web-view页面安卓下显示空白的解决办法!!!
- NOIP2016提高组Day1T2 天天爱跑步 树链剖分 LCA 倍增 差分
- playframework 一步一步来 之 日志 (二)