给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 o(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
思路1：先用二分法找到其中某个target，再向前向后一位一位地找头和尾；
思路2：改进一下，在第二步找头和尾时也用二分法；
#include <iostream> #include <vector> using namespace std; vector<int> searchrange(vector<int>& nums, int target) { vector<int> ans={-1, -1}; if(nums.size()==0) return ans; if(nums.size()==1&&nums[0]==target) return {0,0}; if(nums.size()==1&&nums[0]!=target) return ans; int low=0; int high=nums.size()-1; int mid=0; while(low<=high) { mid=(low+high)/2; if(nums[mid]==target) break; if(target<nums[mid]) high=mid-1; else low=mid+1; } if(low>high) return ans; int begin=mid; int end=mid; low=0; int m1=mid; int m2; while(low<=m1) { m2=(low+m1)/2; if(nums[m2]==target&&(m2-1)>=0&&nums[m2-1]<target) { begin=m2; break; } if(nums[m2]==target&&m2==0) { begin=m2; break; } if(nums[m2]<target&&(m2+1)<=m1&&nums[m2+1]==target) { begin=m2+1; break; } if(nums[m2]==target&&(m2-1)>=0&&nums[m2-1]==target) m1=m2-1; if(nums[m2]<target&&(m2+1)<nums.size()&&nums[m2+1]<target) low=m2+1; } high=nums.size()-1; if((mid+1)<nums.size()&&nums[mid+1]==target) { m1=mid+1; } else return {begin,mid}; while(m1<=high) { m2=(m1+high)/2; if(nums[m2]==target&&(m2+1)<nums.size()&&nums[m2+1]>target) { end=m2; break; } if(nums[m2]==target&&m2==nums.size()-1) { end=m2; break; } if(nums[m2]>target&&(m2-1)>mid&&nums[m2-1]==target) { end=m2-1; break; } if(nums[m2]==target&&(m2+1)<nums.size()&&nums[m2+1]==target) m1=m2+1; if(nums[m2]>target&&(m2-1)>mid&&nums[m2-1]>target) high=m2-1; } return {begin,end}; } int main() { vector<int> a={1,2,3}; int target=1; vector<int> ans=searchrange(a,target); std::cout << ans[0]<<ans[1]<< std::endl; return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/604617.html