驻马店住房和城乡建设局网站,能播放优酷视频的网站怎样做,wordpress文章页宽度,xml用网页打开乱码给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1#xff1a…给你一个按照非递减顺序排列的整数数组 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] 提示
0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109 方法一 class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorint result {-1, -1};int left 0;int right nums.size() - 1;while (left right) { //二分查找算法的核心部分int mid left (right - left) / 2;if (nums[mid] target) {left mid 1;} else {right mid - 1;}}if (left nums.size() nums[left] target) {result[0] left; //找到的话就把起始值记录为left} else {return result; //到了数组结尾还没找到那就直接返回-1-1}right nums.size() - 1; //重置 right 为数组的最后一个索引。while (left right) { //第二次二分查找int mid left (right - left) / 2;if (nums[mid] target) { //这里条件不一样需要注意left mid 1;} else {right mid - 1;}}result[1] right; //更新终止值return result;}
};这道题可以使用二分查找的原因主要在于题目中的数组是非递减顺序排列的整数数组 vectorint result {-1, -1};
初始化一个整数向量 result其初始值为 {-1, -1}。 int mid left (right - left) / 2;
计算当前查找范围的中间索引 mid。这里采用的计算方式是为了避免可能的整数溢出。 if (nums[mid] target)
如果 nums[mid] 小于 target说明目标值位于 mid 的右侧因此将 left 移动到 mid 1缩小查找范围。
如果 nums[mid] 大于或等于 target则目标值位于 mid 的左侧包括 mid 本身所以将 right 移动到 mid - 1缩小查找范围。 left nums.size()
这个条件确保 left 不会超出 nums 数组的范围。因为 left 在查找的过程中可能已经移动到了数组的末尾如果 left 超过了数组的索引范围直接访问 nums[left] 会导致运行时错误。
nums[left] target
这个条件检查 nums[left] 是否等于 target。如果 left 所指向的元素等于目标值说明找到了目标值的起始位置。此时将 result[0] 更新为 left即目标值在数组中的起始索引。 如果 left 不在有效范围内或者 nums[left] 不等于 target这说明数组中不存在目标值。此时直接返回 result它的值仍然是 [-1, -1]表示未找到目标值。 为什么两次二分查找的 if 语句不一样
在第一次二分查找中我们的目标是找到 target 的起始位置。如果存在起始值当left 和 right 相遇时的相遇点即为起始值 target这个时候需要保证 left 为 target就需要right 左移来退出循环。
而在第二次二分查找中我们的目标是找到 target 的结束位置。我们需要保证right 为 target就需要 left右移来退出循坏。 二分查找的精髓通过每次比较中间值来逐步缩小查找范围保证时间复杂度为 O(logn) 方法二
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int start find(nums, target);int end find(nums, target 1) - 1;if (start -1 || end start) {return {-1, -1};}return {start, end};}int find(vectorint nums, int target) {int left 0, right nums.size() - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return left;}
};利用 find(nums, target) 找到 target 的第一个位置再利用 find(nums, target 1) 找到比 target 大的第一个元素的位置从而间接确定 target 的结束位置。 如果数组中不存在第一个大于 target 的元素那么 find(nums, target 1) 的结果将会是 nums.size()end的值为 nums.size() - 1 假设 nums [5, 7, 7, 8, 8, 10]target 8
find(nums, 8) 返回 3因为 8 的第一个位置在索引 3。find(nums, 9) 返回 5因为 9 比 8 大且索引 5 是第一个大于 8 的位置。end find(nums, 9) - 1 等于 4所以返回 [3, 4]。
