当前位置:网站首页>[leetcode]Search for a Range
[leetcode]Search for a Range
2022-07-06 18:48:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
问题叙述性说明:
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order ofO(log n).
If the target is not found in the array, return [-1, -1]
.
For example, Given [5, 7, 7, 8, 8, 10]
and target value 8, return [3, 4]
.
基本思路:
此题能够用二分查找法解决。
假设数组中没有target,能够在O(lgn)时间完毕。
假设数组中有target,当发现target后,对前后的内容继续用二分法 查找这种位置pos 。
- 前面的pos须要满足 A[pos] < target && A[pos+1] == target. pos+1即是開始位置。
- 后面的pos须要满足 A[pos] > target && A[pos-1] == target . pos-1是结束位置。
代码:
vector<int> searchRange(int A[], int n, int target) { //C++
vector<int> result(2);
int low = 0, high = n-1;
int mid, begin = -1, end = -1;
while(low <= high)
{
mid = (low+high)/2;
if(A[mid] > target)
high = mid - 1;
else if(A[mid] < target)
low = mid + 1;
else
{
begin = mid;
end = mid;
//get begin
if(low <= begin -1){
while((low <= begin-1) && !(A[low]<target && A[low+1] == target) )
{
mid = (low + begin-1)/2;
if(A[mid] < target)
low = mid+1;
else begin = mid;
}
if(A[low]<target && A[low+1] == target)
begin = low+1;
}
//get end
if(high >= end+1){
while((high >= end+1) &&!(A[high]>target && A[high-1] == target))
{
mid = (high + end +1)/2;
if(A[mid] > target)
high = mid - 1;
else end = mid;
}
if(A[high]>target && A[high-1] == target)
end = high - 1;
}
break;
}
}
result[0] = begin;
result[1] = end;
return result;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116862.html原文链接:https://javaforall.cn
边栏推荐
- Summer Challenge database Xueba notes (Part 2)~
- Pgadmin4 of PostgreSQL graphical interface tool
- 真实项目,用微信小程序开门编码实现(完结)
- [server data recovery] data recovery case of a Dell server crash caused by raid damage
- 【森城市】GIS数据漫谈(二)
- 低代码平台中的数据连接方式(上)
- New generation cloud native message queue (I)
- [C # notes] reading and writing of the contents of text files
- Word wrap when flex exceeds width
- 新一代云原生消息队列(一)
猜你喜欢
leetcode:5. 最长回文子串【dp + 抓着超时的尾巴】
Time synchronization of livox lidar hardware -- PPS method
Data connection mode in low code platform (Part 1)
Draco - gltf model compression tool
老板被隔离了
How can reinforcement learning be used in medical imaging? A review of Emory University's latest "reinforcement learning medical image analysis", which expounds the latest RL medical image analysis co
FLIR blackfly s usb3 industrial camera: white balance setting method
The last line of defense of cloud primary mixing department: node waterline design
1个月增长900w+播放!总结B站顶流恰饭的2个新趋势
FLIR blackfly s usb3 industrial camera: how to use counters and timers
随机推荐
建議收藏!!Flutter狀態管理插件哪家强?請看島上碼農的排行榜!
猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
【论文阅读|深读】DNGR:Deep Neural Networks for Learning Graph Representations
How to build a 32core raspberry pie cluster from 0 to 1
Lombok makes the pit of ⽤ @data and @builder at the same time
ODBC database connection of MFC windows programming [147] (with source code)
Draco - glTF模型压缩利器
4 -- Xintang nuc980 mount initramfs NFS file system
Draco - gltf model compression tool
Tips for web development: skillfully use ThreadLocal to avoid layer by layer value transmission
阿里云易立:云原生如何破解企业降本提效难题?
[C # notes] use file stream to copy files
Zhang Ping'an: accelerate cloud digital innovation and jointly build an industrial smart ecosystem
C语言练习题_1
Lombok同时使⽤@Data和@Builder 的坑
How do I dump SoapClient requests for debugging- How to dump SoapClient request for debug?
1 -- Xintang nuc980 nuc980 porting uboot, starting from external mx25l
leetcode:736. LISP syntax parsing [flowery + stack + status enumaotu + slots]
Integerset of PostgreSQL
unity webgl自适应网页尺寸