刷题34. Find First and Last Position of Element in Sorted Array
2024-08-31 12:21:51
一、题目说明
题目是34. Find First and Last Position of Element in Sorted Array，查找一个给定值的起止位置，时间复杂度要求是Olog(n)。题目的难度是Medium！
二、我的解答
这个题目还是二分查找（折半查找），稍微变化一下。target==nums[mid]后，需要找前面、后面的值是否=target。
一次写出来，bug free，熟能生巧！怎一个爽字了得！
#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:
vector<int> searchRange(vector<int>& nums, int target){
vector<int> res;
if(nums.size()<1){
res.push_back(-1);
res.push_back(-1);
return res;
}
int begin = 0;
int end = nums.size()-1;
int mid = -1;
while(begin <= end){
mid = (begin + end) / 2;
if(nums[mid] == target){
begin = mid;
while(begin>0 && nums[begin] == target){
begin--;
}
if(nums[begin]==target){
res.push_back(begin);
}else{
res.push_back(begin+1);
}
end = mid;
while(end<nums.size()-1 && nums[end] == target){
end++;
}
if(nums[end]==target){
res.push_back(end);
}else{
res.push_back(end-1);
}
return res;
}else if(nums[mid] < target){
begin = mid + 1;
}else{
end = mid - 1;
}
}
//未找到
res.push_back(-1);
res.push_back(-1);
return res;
}
};
int main(){
Solution s;
vector<int> nums = {5,7,7,8,8,10};
vector<int> r = s.searchRange(nums,8);
for(vector<int>::iterator it=r.begin();it!=r.end();it++){
cout<<*it<<" ";
}
r = s.searchRange(nums,6);
for(int i=0;i<r.size();i++){
cout<<r[i]<<" ";
}
return 0;
}
代码性能：
Runtime: 12 ms, faster than 38.75% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 10.4 MB, less than 70.33% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
三、改进
上一个题目，发现mid = begin + (end - begin) / 2; ，性能比mid = (begin + end) / 2高很多。
性能提高到：
Runtime: 8 ms, faster than 86.11% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 10.4 MB, less than 82.42% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
这究竟为何，哪位大神指导，请指点。不胜感激！！！
此处不要提mid = (begin + end) / 2可能溢出。。。
最新文章
- listview指定某item的点击效果
- 【php常用】常用函数啥的
- Spring利器之包扫描器
- JavaScript---基本语法
- （实用篇）php处理单文件、多文件上传代码分享
- （转）Linux内核之进程和系统调用
- LFS：kernel panic VFS: Unable to mount root fs
- Apache 实现ProxyPass转发URL到Tomcat并实现http自动转https【转载】
- spring源码浅析——IOC
- java 动态代理 ， 多看看。 多用用。
- python1.返回一个字符串中出现次数第二多的单词 2.字符串中可能有英文单词、标点、空格 3.字符串中的英文字符全部是小写
- Kafka技术内幕 读书笔记之（四） 新消费者——消费者提交偏移量
- Python源码中的PyCodeObject
- KafkaManager对offset的两种管理方式
- Docker：bash: vi: command not found
- sqlserver修改主键为自增
- 半屏控制器,view: UIViewController+KNSemiModal
- Qt画笔实现折线图
- SQLServer 中的身份验证及登录问题
- JVM总结（一）：概述--JVM运行时数据区