当前位置:网站首页>Record of force deduction and question brushing 3---34 Find the first and last positions of elements in a sorted array
Record of force deduction and question brushing 3---34 Find the first and last positions of elements in a sorted array
2022-07-21 01:38:00 【@Bai Gui】
One 、 subject
Two 、 Code
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int size= nums.size();
//std::cout<<sz<<std::endl;
int left=0;
int right=size-1;
int middle=0;
vector<int> return_vector; // The use of iterators , You have to use push_back() perhaps ={} initialization , Can only be
return_vector={
-1,-1};
int fist_dst=-1; // The starting position
int last_dst=-1; // Termination position
int middle_dst=-1; // First found location
while(left<=right)
{
if(left<=right-2) // Two points can be divided
{
middle=(left+right)/2; // The questions are arranged in ascending order
if(nums[middle]==target) // Equal after two points Return index value
{
middle_dst=middle;
break;
}
if(nums[middle]>target) // The value after two points is larger than the target value The middle value must not be On the left
{
right=middle-1;
}
if(nums[middle]<target) // The value after two points is smaller than the target value The middle value must not be In zip code
{
left=middle+1;
}
}
else // Two cannot be separated The two are equal or different 1
{
if(nums[left]==target)
{
middle_dst=left;
break;
}
if(nums[right]==target)
{
middle_dst=right;
break;
}
if(nums[right]!=target&&nums[left]!=target) break;
}
}
// At this time, one coordinate has been found or none has been found
int i;
std::cout<<"temp middle_dst" <<middle_dst<<std::endl;
if(middle_dst!=-1)
{
for(i=middle_dst;i>=1;i--) // Looking for the left boundary
{
if(nums[i]==target&&nums[i-1]!=target)
{
fist_dst=i;
break;
}
if(nums[0]==target)
{
fist_dst=0;
break;
}
}
for(i=middle_dst;i<=size-2;i++) // Look for the right border
{
if(nums[i]==target&&nums[i+1]!=target)
{
last_dst=i;
break;
}
if(nums[size-1]==target)
{
last_dst=size-1;
break;
}
}
// As long as it can enter the cycle We must be able to find the left and right boundaries Next, consider the situation that you can't enter the left-right cycle
if(middle_dst==0) // Left boundary lookup Leak filling
{
if(nums[0]==target) fist_dst=0;
}
if(middle_dst>size-2)
{
if(nums[size-1]==target) last_dst=size-1;
}
}
return_vector[0]=fist_dst;
return_vector[1]=last_dst;
return return_vector;
}
};
3、 ... and 、 Running results
边栏推荐
猜你喜欢
Resolved no module named 'flask_ Misaka '[bug solution]
Miller gingival recession and mucogingival junction
cannot import name ‘import_string‘ from ‘werkzeug‘【bug解决】
力扣刷题14. 最长公共前缀
LeetCode_ 78_ subset
Infraversion and superversion
20元一支的洗面奶,7天卖了上万,他们是如何做到的?
How to build a simple and secure enterprise internal file server?
一条代码带大家绘制交互式+pdf+png等多格式桑基美图
力扣343-整数分割——动态规划
随机推荐
私域流量和裂变营销的关系,什么是超级APP,我们企业能拥有吗?
LeetCode.1217. 玩筹码____简单贪心
LeetCode.745. 前缀和后缀搜索____双字典树+双指针
剑指 Offer II 041. 滑动窗口的平均值_____使用队列 / 循环数组实现
网络安全—综合渗透测试-CVE-2018-10933-libssh漏洞分析
Unity:PC开发,鼠标点击物体触发物体更换材质
网络安全—综合渗透测试-CVE-2019-15107-Webmin远程代码执行
CCleaner的使用
力扣刷题记录1-----704.二分查找
Map/Multimap 容器的系列操作
VMware安装
Light up through TCP
Visio使用
Tutorial on principles and applications of database system (032) -- data integrity of MySQL (V): define auto_increment
中职网络安全技能大赛P100-mssql数据库渗透测试
数据库系统原理与应用教程(029)—— MySQL 的数据完整性(二):定义主键(primary key)
Network security - comprehensive penetration test -cve-2019-15107-webmin remote code execution
如何搭建简易又安全的企业内部文件服务器?
How to build a simple and secure enterprise internal file server?
Create a file. If the superior (or superior, etc.) directory of the file does not exist, create the superior directory first, and then create the file