石家庄做网站电话,php做网站 价格,cms系统网站,爱站云网站建设heikw1. 题目解析
Leetcode链接#xff1a;34. 在排序数组中查找元素的第一个和最后一个位置 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了。
核心在于找到给定目标值所在的数组下标区间#xff0c;设计一个O(logn)的算法。 2. 算法原…1. 题目解析
Leetcode链接34. 在排序数组中查找元素的第一个和最后一个位置 这个问题的理解其实相当简单只需看一下示例基本就能明白其含义了。
核心在于找到给定目标值所在的数组下标区间设计一个O(logn)的算法。 2. 算法原理
寻找左边界思路
目标找到数组中第一个大于或等于目标值的元素的索引。
特点
左边区间 [left, resLeft - 1] 的所有元素都小于 target。右边区间包括 resLeft[resLeft, right] 的所有元素都大于等于 target。
二分查找步骤
初始化 left 和 right 为数组的开始和结束索引。计算中间索引 mid注意向下取整。根据 arr[mid] 与 target 的关系调整 left 或 right 的值。 如果 arr[mid] target则更新 left mid 1。如果 arr[mid] target则更新 right mid。重复步骤 2 和 3直到 left right。返回 left 或 right取决于具体实现。
注意当 right mid 时应向下取整以防止死循环。
寻找右边界思路
目标找到数组中最后一个大于或等于目标值的元素的索引。
特点
左边区间 [left, resRight] 的所有元素都小于等于 target。右边区间 [resRight 1, right] 的所有元素都大于 target。
二分查找步骤
初始化 left 和 right 为数组的开始和结束索引。计算中间索引 mid注意向上取整。根据 arr[mid] 与 target 的关系调整 left 或 right 的值。 如果 arr[mid] target则更新 left mid。如果 arr[mid] target则更新 right mid - 1。重复步骤 2 和 3直到 left right。返回 right 或 left取决于具体实现。
注意当 right mid 时应向上取整以防止死循环。
通过合理地调整 left 和 right 的值二分查找可以高效地找到左边界和右边界。 3. 代码编写
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int left 0, right nums.size() - 1, begin -1, end -1, mid;//找到区间左边界while(leftright){mid (left right)/2;if(nums[mid] target){right mid - 1;}else if(nums[mid] target){left mid 1;}else{begin mid;right--;//right区间左移使得mid左移直到到达左区间边界此时right正好和left重合}}left 0, right nums.size() - 1;//找到区间有边界while(leftright){mid (left right)/2;if(nums[mid] target){right mid - 1;}else if(nums[mid] target){left mid 1;}else{end mid;left;//left区间右移使得mid右移直到到达又区间边界此时left正好和right重合}}return {begin,end};}
}; The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
