马克杯网站开发,绍兴网站制作计划,讨债公司 做网站,有什么网站可以做名片一#xff1a;题目
给定一个按照升序排列的整数数组 nums#xff0c;和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。
进阶#xff1a;
你可以设计并实现时间复杂度为 O(log n) 的算法解…一题目
给定一个按照升序排列的整数数组 nums和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
进阶
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗
示例 1
输入nums [5,7,7,8,8,10], target 8 输出[3,4] 示例 2
输入nums [5,7,7,8,8,10], target 6 输出[-1,-1] 示例 3
输入nums [], target 0 输出[-1,-1]
二:思路
思路:1.我们求取给定数组范围内 目标值的左边界和右边界 2.拿下方的例子来解释: nums [5,7,7,8,8,10], target 8 3.左边界指的就是数组当中的元素值都小于等于目标值的范围5,7,7,8 右边界指的是数组当中的元素值都大于等于目标值的范围8,10 4.当我们求出目标值的左右边界也就求出了题目说的开始和结束位置
三上码
方法一二分法
class Solution {
public:vectorint searchRange(vectorint v, int target) {//方法二:二分法/*思路:1.我们求取给定数组范围内 目标值的左边界和右边界2.拿下方的例子来解释:nums [5,7,7,8,8,10], target 83.左边界指的就是数组当中的元素值都小于等于目标值的范围5,7,7,8右边界指的是数组当中的元素值都大于等于目标值的范围8,104.当我们求出目标值的左右边界也就求出了题目说的开始和结束位置 */int l left_border(v,target);int r right_border(v,target);if(l -3 || r -3){//证明根本就无该目标值 比如[3,4,6] 找 7return {-1,-1};}if(v[l1] target v[r-1] target)//得保证查询到的元素存在return {l1,r-1};//其他情况return{-1,-1};}//求取左边界即数组当中均小于目标值的范围int left_border(vectorint v, int target){int l 0;int r v.size() - 1;int mid;int temp -3;while(l r){mid (lr)/2;if(v[mid] target){//这是结束的条件,因为已经出现要大于等于目标值的元素了r mid - 1;temp r;}else{l mid 1;//不断接近目标值}}return temp;}//求取右边界即数组当中的元素均大于目标值的范围int right_border(vectorint v, int target){int l 0;int r v.size() - 1;int mid;int temp -3;while(l r){mid (lr)/2;if(v[mid] target){r mid - 1;//不断缩小范围接近目标值从数组的右边来}else{l mid 1;//证明查找到了出现小于等于目标值的元素时这时循环也就结束了因为 l rtemp l;}} return temp;}}; 方法二调用库函数lower_bound,upper_bound
注意调用库函数的区别
lower_bound(开始位置,结束位置目标值) - 开始位置 这个返回的是元素第一次出现的位置如果查询不到目标值则返回第一个比起大的元素下标 upper_bound(开始位置,结束位置目标值) - 开始位置 这个返回的是有元素第一次大于目标值的位置所以在本题中 要减一
注意这是升序数组当中调用的函数
我自己在测试用例时用了个非升序的例子害。。。。。。结果。。省略一万句。。。
class Solution {
public:vectorint searchRange(vectorint v, int target) {// /**// 注意前提条件是输入的数值是升序的 // */ //方法一利用库函数// //查询某个元素第一次出现的下标 int l lower_bound(v.begin(),v.end(),target) - v.begin();if( l v.size() || v[l] ! target){ return {-1,-1};}//返回的是第一个大于待查数值的地址int r upper_bound(v.begin(),v.end(),target) - v.begin(); return {l,r-1};}}; 四补充vector中lower_bound(),upper_bound()的用法测试用例
#includebits/stdc.h
using namespace std;int main(){vectorintv;int N,a;cin N a ;for(int i 0; i N; i){int temp;cin temp;v.push_back(temp); } /**注意前提条件是输入的数值是升序的 */ //查询某个元素第一次出现的下标如果查询不到目标值则返回第一个比起大的元素下标int l lower_bound(v.begin(),v.end(),a) - v.begin();//返回的是第一个大于待查数值的地址 int r upper_bound(v.begin(),v.end(),a) - v.begin();cout l r - 1;} //6 3
//1 2 3 4 4 5 //6 9
//5 7 7 8 8 10拿走不用谢
最后在啰嗦啰嗦最好不要用库函数这道题其实就是考察二分法的运用对于这个库函数其实知道就行可以将他用到你写的其他码上本题不建议使用
好了 就这样加油 BOY!!! and girl
