题目描述
统计一个数字在排序数组中出现的次数。
示例 1:
1
2
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
解题
方法 1
二分法找 target 和 target - 1 的右边界，taget 数量为 target 的右边界 - target - 1 的右边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
int binarySearch(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while ( l <= r ) {
int mid = l + (r - l) / 2;
if ( nums[mid] <= target ) l = mid + 1;
else r = mid - 1;
}
return l;
}
public:
int search(vector<int>& nums, int target) {
return binarySearch(nums, target) - binarySearch(nums, target - 1);
}
};
复杂度分析：
时间复杂度 O(log2N) ： 二分查找 N 个元素的数组，时间为 O(log2N)
空间复杂度 O(1) ： 没有使用额外的存储
方法 2
查找 target 的左右边界
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
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
int left = nums.size();
while ( l <= r ) {
int mid = l + (r - l) / 2;
if ( nums[mid] < target ) l = mid + 1;
else {
r = mid - 1;
left = mid;
}
}
l = 0;
r = nums.size() - 1;
int right = nums.size();
while ( l <= r ) {
int mid = l + (r - l) / 2;
if ( nums[mid] <= target ) {
l = mid + 1;
right = mid;
} else r = mid - 1;
}
//right = right - 1;
if ( left < nums.size() && right < nums.size() && nums[left] == target && nums[right] == target ) {
return right - left + 1;
}
return 0;
}
};
复杂度分析：
时间复杂度 O(log2N) ： 二分查找 N 个元素的数组，时间为 O(log2N)
空间复杂度 O(1) ： 没有使用额外的存储
写在最后
感谢你在茫茫人海中找到我🕵🏼
🎉你是第 个读者
㊗️ 你平安喜乐，顺遂无忧！
希望你读完有所收获～