数组中删除一个元素?难度:中等
看到题目我们需要知道以下几点:
根据题目要求,算法复杂度必须是O(logn)级别,那么二分法就是最佳的算法。根据本题,我们要寻找的是目标元素在数组的起始位置和结束位置,我们可以根据二分法先搜索目标元素的起始位置,然后以该起始位置为起点,在搜索结束位置即可。时间复杂度为O(logn)
js删除数组中的元素?代码如下:
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> res(2,-1);// 如果数组为空,直接返回[-1,-1]if(nums.empty()) return res;// 初始化变量int n=nums.size(),l=0,r=n-1;// 循环条件是左下标<右下标while(l<r){int m=l+(r-l)/2;if(nums[m]>=target) r=m;else l=m+1;}// 如果nums[l]!=target,说明目标不存在,返回[-1,-1]if(nums[l]!=target) return res;// 否则l即目标元素的起始位置res[0]=l;// 寻找右节点r=n;while(l<r){int m=l+(r-l)/2;if(nums[m]<=target) l=m+1;else r=m;}res[1]=l-1;return res;}
};
运行结果为:
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态