网站空间可以自己买吗,做网站服务好,专业seo推广,网址软件下载文章目录 力扣题目代码 力扣题目
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算… 文章目录 力扣题目代码 力扣题目
给你一个按照非递减顺序排列的整数数组 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] 109 nums 是一个非递减数组 -109 target 109
代码
思路分析使用两次查找 1.第一次找到第一个target的位置 2.第二次找到最后一个target的位置 3.需要特别注意的是第一次查找找到target时做的right mid - 1;以及第二次查找找到target时做的left mid 1;这两次的操作特别重要。只有这样才能找两遍target的边界值。代码中也写了详细的注释希望大家认真看一下。
int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{int first -1, last -1;int left 0, right numsSize - 1, mid 0;int* arr (int*)malloc(sizeof(int) * 2);/*查找一个等于target的位置*/while (left right){mid left (right - left) / 2;if (nums[mid] target){first mid;/*查看mid位置的左侧是否还有等于target的值确保first的的索引是第一个target的位置*/right mid - 1;}else if (nums[mid] target){right mid - 1;}else{left mid 1;}}left 0;right numsSize - 1;/*查找最后一个等于target的位置*/while (left right){mid left (right - left) / 2;if (nums[mid] target){last mid;/*查看mid位置的右侧是否还有等于target的值确保last的的索引是最后一个target的位置*/left mid 1;}else if (nums[mid] target){right mid - 1;}else{left mid 1;}}*returnSize 2;arr[0] first;arr[1] last;return arr;
}
