当前位置:网站首页>2022-7-7 Leetcode 34.在排序数组中查找元素的第一个和最后一个位置
2022-7-7 Leetcode 34.在排序数组中查找元素的第一个和最后一个位置
2022-07-07 11:36:00 【weixin_51187533】
1、左右区间要单独查找,时间复杂度为 O ( l o g N ) O(logN) O(logN)
2、查找右边界的时候,左边向右收缩;查找左边界的时候,右边向左收缩。
class Solution {
public:
int getR(vector<int>& nums, int target){
int l = 0, r = nums.size()-1;
int rightborder = -1;
while (l <= r){
int mid = l + (r - l)/2;
if (nums[mid] == target){
l = mid + 1;
rightborder = mid;
}else if (nums[mid] > target){
r = mid - 1;
}else {
l = mid + 1;
}
}
return rightborder;
}
int getL(vector<int>& nums, int target){
int l = 0, r = nums.size()-1;
int leftborder = -1;
while (l <= r){
int mid = l + (r - l)/2;
if (nums[mid] == target){
r = mid - 1;
leftborder = mid;
}else if (nums[mid] > target){
r = mid - 1;
}else {
l = mid + 1;
}
}
return leftborder;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftborder = getL(nums, target);
int rightborder = getR(nums, target);
return {
leftborder, rightborder};
}
};
边栏推荐
- [learning notes] zkw segment tree
- MongoDB优化的几点原则
- 【面试高频题】难度 2.5/5,简单结合 DFS 的 Trie 模板级运用题
- Show the mathematical formula in El table
- How far can it go to adopt a cow by selling the concept to the market?
- 如何让electorn打开的新窗口在window任务栏上面
- MongoDB内部的存储原理
- LeetCode_ Binary search_ Medium_ 153. Find the minimum value in the rotation sort array
- 【黑马早报】华为辟谣“军师”陈春花;恒驰5预售价17.9万元;周杰伦新专辑MV 3小时播放量破亿;法华寺回应万元月薪招人...
- 信号强度(RSSI)知识整理
猜你喜欢
随机推荐
记一次 .NET 某新能源系统 线程疯涨 分析
《厌女:日本的女性嫌恶》摘录
Solve the cache breakdown problem
Milkdown 控件图标
QQ medicine, Tencent ticket
1. Deep copy 2. Call apply bind 3. For of in differences
Simple and easy-to-use code specification
Why can basic data types call methods in JS
Cinnamon 任务栏网速
User management summary of mongodb
SSRF漏洞file伪协议之[网鼎杯 2018]Fakebook1
Custom thread pool rejection policy
简单好用的代码规范
Introduction and basic use of stored procedures
Clion mingw64 Chinese garbled code
实现IP地址归属地显示功能、号码归属地查询
PAcP learning note 3: pcap method description
High end for 8 years, how is Yadi now?
ESP32构解工程添加组件
MongoDB命令汇总