LeetCode #34 - Find First and Last Position of Element in Sorted Array
1519 ワード
タイトルの説明:
Given an array of integers
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return
Example 1:
Example 2:
O(log n)の時間的複雑度で秩序配列でなければならないので,二分探索を考慮する.ターゲット要素が見つかったら、それぞれ両側に検索し、その要素の最初の位置と最後の位置を見つけます.
Given an array of integers
nums
sorted in ascending order, 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
[-1, -1]
. Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
O(log n)の時間的複雑度で秩序配列でなければならないので,二分探索を考慮する.ターゲット要素が見つかったら、それぞれ両側に検索し、その要素の最初の位置と最後の位置を見つけます.
class Solution {
public:
vector searchRange(vector& nums, int target) {
int begin=0;
int end=nums.size()-1;
int mid=(begin+end)/2;
while(begin<=end)
{
if(nums[mid]==target)
{
int i=mid;
int j=mid;
while(nums[i-1]==target&&i>0) i--;
while(nums[j+1]==target&&j result;
result.push_back(i);
result.push_back(j);
return result;
}
else if(target>nums[mid])
{
begin=mid+1;
mid=(begin+end)/2;
}
else if(target(2,-1);
}
};