做网站免费服务器哪家好,工厂网络设计方案,博客网站开发视频,建设部监理工程师网站个人主页#xff1a;Lei宝啊
愿所有美好如期而遇 目录
本题链接
输入描述
输出描述
算法分析
1.算法一#xff1a;暴力求解
2.算法二#xff1a;朴素二分算法
3.算法三#xff1a;二分查找左右端点
3.1查找左端点
3.1.1细节一#xff1a;循环条件
3.1.2细节二… 个人主页Lei宝啊
愿所有美好如期而遇 目录
本题链接
输入描述
输出描述
算法分析
1.算法一暴力求解
2.算法二朴素二分算法
3.算法三二分查找左右端点
3.1查找左端点
3.1.1细节一循环条件
3.1.2细节二mid的值
3.2查找右端点
解题源码 本题链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
输入描述
我们选择示例1接口为vectorint searchRange(vectorint nums, int target) 向nums中写入非递减的数字也就是说可以有多个重复的相同数字。
输出描述
由于nums中可能有多个值与target相等所以我们需要记录这个区间的左端点和右端点然后返回这个区间如果找不到则区间为[-1,-1]。
算法分析
1.算法一暴力求解
直接从左到右扫描这个数组通过begin和end变量来记录相等于target的起始位置和结束位置找不到则返回[-1,-1]时间复杂度为O(N)。
2.算法二朴素二分算法
直接二分如果寻找的target在nums中只有一个那么时间复杂度为log(N)但是如果有多个的话我们还是需要去遍历mid的左边和mid的右边如果整个数组所有值都与target相等就相当于要遍历整个数组时间复杂度仍然为O(N)这里我们使用朴素二分算法仍然不是最优的。
3.算法三二分查找左右端点
3.1查找左端点
我们可以将数组分成两个区间以[5,7,7,8,8,10],target 8为例既然我们要找左端点也就是最左边的那个8所以我们将数组分成小于target的区间和大于等于target的区间即[5,7,7] [8,8,10]这两个区间。(lhs意为left side hand即左手边rhs意为right side hand即右手边) 我们定义一个midmid lhs (rhs - lhs) / 2并且有两种结果
当nums[mid] target lhs mid 1;当nums[mid] target, rhs mid;
你可能会问为什么rhs mid, 按照我们朴素二分算法的理解应该是rhs mid - 1, 我们可以举个例子如果说mid 3,也就是上面最左边的8那么再怎么样我们也无法找到左端点了。
同时按照我们上面的两种结果我们也可以发现一个事实就是rhs永远不会出他的区间lhs是可以跨区间的当lhs rhs时也就代表着循环结束了。
所以这就是全部了吗当然不是他还有其他细节这些细节一但注意不到就是一个接一个的死循环。
3.1.1细节一循环条件
朴素二分算法循环条件是lhs rhs那么我们这里也是这样吗上面我们提过一个事实就是说当lhs rhs时就已经结束了而且正好是我们的左端点所以说我们不用再去判断相等的情况你可能会说碰巧罢了你这是能找到结果你要是找不到呢如果nums里全部大于target呢如果nums里全部小于target呢那我们分三种情况: 所以我们不需要判断lhs rhs这种情况因为我们上述三种情况就是本题的所有情况而我们也证实了当lhs rhs时就是我们的结果要么找到要么就找不到。
但是有人会犯倔我嫌麻烦还得想这么多东西不就多判断一次嘛我就用lhs rhs 有问题吗还是分三种情况运气好点就不死循环。 所以我们循环条件也有两个细节
细节一无需判断lhs rhs因为此时已经是结果了。细节二 如果真的比较了可能会死循环在leetcode众多测试用例中一定是错的。
3.1.2细节二mid的值
我们上面直接让mid lhs (rhs - lhs) / 2; 可能你也没有思考为什么可不可以事实上在查找左端点时这样正好可以但是放在查找右端点上就是死循环那么右端点mid怎么算
mid lhs (rhs - lhs 1) / 2;那么我们把这个用在左端点上看看效果。 我们可以发现
选择第一种方式mid的值偏向于左边下标选择第二种方式mid的值偏向于右边下标
细节很多不注意就死循环但是我们不要死记硬背要去理解怎么样就死循环了这才是我们该做的。
3.2查找右端点
查找右端点和查找左端点思路完全相同只是有些细节不同我们这里指出
区间的划分大于target的区间的小于等于target的区间mid的计算mid lhs (rhs - lhs 1) / 2;
剩下的就是一个模子了。
解题源码
class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorint v(2,-1);if(nums.size() 0) return v;//计算左端点int lhs 0, rhs nums.size() - 1, mid lhs (rhs - lhs) / 2;while(lhs rhs){//分区间if(nums[mid] target) lhs mid 1; //小于区间else rhs mid; //大于等于区间 mid lhs (rhs - lhs) / 2;}if(nums[rhs] target) v[0] rhs;//计算右端点lhs 0, rhs nums.size() - 1, mid lhs (rhs - lhs 1) / 2;while(lhs rhs){//分区间if(nums[mid] target) rhs mid - 1; //大于区间else lhs mid; //小于等于区间 mid lhs (rhs - lhs 1) / 2;}if(nums[rhs] target) v[1] rhs;return v;}
};
