个人网站有哪些平台,做网上商城网站,中小型企业网络部署,如何网页设计与制作文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。
你必须设计… 文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 提示 2.解答思路
提取信息 1.时间复杂度必须为O(logn) 2.没查找到时返回{-1-1}查找到就返回下标
本题难点二分查找的实现 查找第一个小于target和第一个大于target的值
3.实现代码
class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorintans;int nnums.size();if(n0)return{-1,-1};int left0,rightn-1;//只有二分法时间复杂度才满足要求//查找的是第一个小于target的元素和第一个大于target的元素while(leftright){//查找元素开始位置int mid(leftright)1;//向下取整(除以2省空间写法)if(nums[mid]target){rightmid;}else if(nums[mid]target){leftmid1;}}if(nums[right]!target)return{-1,-1};//查找失败ans.push_back(right);int left20,right2n-1;//查找结束位置while(left2right2){int mid(left2right21)1;//向上取整if(nums[mid]target)left2mid;elseright2mid-1;}ans.push_back(right2);return ans;}
};结果 用时约两个小时目前的解法性能不是很好有时间继续改进。
4.总结
本来以为挺简单的一道题题不可貌相。 限定的时间复杂度决定了只能使用二分查找二分查找的细节还需要好好整理一下再完善该题。
自信坚持upup
