题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
题解
首先想到的是二分法找到一个target的值，然后再以此为起点，分别往前和往后找，确定target出现的开始位置和结束位置。 但这样做的是时间度是O(logn + n)即O(n)，不符合题目中O(logn)的要求。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int beg = 0, end = nums.size() - 1, mid, l_idx = -1, r_idx = -1;
while(beg <= end){
mid = (beg + end) / 2;
if(nums[mid] < target){
beg = mid + 1;
}
else if(nums[mid] > target){
end = mid - 1;
}
else{
break;
}
}
if(beg > end){
l_idx = r_idx = -1;
}
else{
l_idx = mid;
while(l_idx >= 0 && nums[l_idx] == target){
--l_idx;
}
++l_idx;
r_idx = mid;
while(r_idx < nums.size() && nums[r_idx] == target){
++r_idx;
}
--r_idx;
}
return vector<int>{l_idx, r_idx};
}
};
|
执行结果
优化
两次二分，第一次二分找到某个target的位置pos，将l_idx与r_idx的值更新为pos,然后第二次二分分为两部分：左半边二分找到target更新l_idx,beg1 > end1结束；右半边找到target更新r_idx，beg2 > end2结束。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int beg = 0, end = nums.size() - 1, mid, l_idx = -1, r_idx = -1;
int beg1, end1, beg2, end2, mid1, mid2;
while(beg <= end){
mid = (beg + end) / 2;
if(nums[mid] < target){
beg = mid + 1;
}
else if(nums[mid] > target){
end = mid - 1;
}
else{
break;
}
}
if(beg <= end){
l_idx = mid;
r_idx = mid;
beg1 = beg;
end1 = mid - 1;
beg2 = mid + 1;
end2 = end;
while(beg1 <= end1){
mid1 = (beg1 + end1) / 2;
if(nums[mid1] < target){
beg1 = mid1 + 1;
}
else{
l_idx = mid1;
end1 = mid1 - 1;
}
}
while(beg2 <= end2){
mid2 = (beg2 + end2) / 2;
if(nums[mid2] > target){
end2 = mid2 - 1;
}
else{
r_idx = mid2;
beg2 = mid2 + 1;
}
}
}
return vector<int>{l_idx, r_idx};
}
};
|
执行结果
