长安东莞网站设计,宁波网站设计相信荣胜网络,建设六马路小学网站,如何建设专业化的网站某个大厂面试手撕代码遇到的题#xff0c;血泪的教训#xff1a;
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。
你必须设计…某个大厂面试手撕代码遇到的题血泪的教训
给你一个按照非递减顺序排列的整数数组 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
注意时间复杂度为 O(log n) 所以想到用二分查找
class Solution {
public:vectorint searchRange(vectorint nums, int target) { int len, start, end, mid;len nums.size();start 0;end len - 1;vectorint arr(2,-1); //初始化一个[-1,-1]的数组if(len 0) return arr;while(startend){mid (start end)/2;if(target nums[mid]){ //target等于中间值则下面往两边进行查找int i mid;int j mid;while((i0) (nums[i] target)) i--; //往左查找因为是有序数组相等的值会挨在一起直到出现不等的值if(i0) arr[0] 0;else arr[0] i 1;while((jlen-1)(nums[j] target)) j;//同理往右查找if(jlen-1) arr[1] len - 1;else arr[1] j - 1;return arr;}else if(target nums[mid]){start mid 1;}else if(target nums[mid]){end mid - 1;}} return arr; //nums中没有查找到target返回[-1,-1]}
};
