国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > [LeetCode] Search for a Range

[LeetCode] Search for a Range

来源:程序员人生   发布时间:2015-07-24 09:27:01 阅读次数:3749次

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [⑴, ⑴].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

解题思路:

这道题的题意是找到排序数组中目标值的下标范围,这个数组可能会有相同的元素。

题目要求时间复杂度在O(logn)。3次2分查找。第1次找到1个值为target的下标k,第2次找到0~k中值为target的最小下标,第3次找到k~len⑴中值为target的最大下标。每次的时间复杂度为O(logn)。

class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> result({⑴, ⑴}); int start=0, end=nums.size()⑴; int middle; //找到第1个 while(start<=end){ middle=(start+end)/2; if(nums[middle]==target){ result[0]=result[1]=middle; break; }else if(nums[middle]>target){ end=middle⑴; }else{ start=middle+1; } } if(result[0]!=⑴){ //找到最小的那个下标 start=0; end=result[0]⑴; while(start<=end){ middle=(start+end)/2; if(nums[middle]==target){ end=middle⑴; result[0]=middle; }else{ start=middle+1; } } //找到最大的那个下标 start=result[1]+1; end=nums.size()⑴; while(start<=end){ middle=(start+end)/2; if(nums[middle]==target){ start=middle+1; result[1]=middle; }else{ end=middle⑴; } } } return result; } };


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生