即使输掉了一切，也不要输掉微笑。
题目
参考LCR 172. 统计目标成绩的出现次数。
某班级考试成绩按非严格递增顺序记录于整数数组 scores，请返回目标成绩 target 的出现次数。示例 ：
输入: scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出: 3
解题思路
-
两次二分：简单的做法是直接统计时间复杂度为
O(n)较高，本题因为scores有序所以可使用二分查找降低时间复杂度到O(logn)。需要两次二分，分别查找target的开始位置和结束位置，同时注意判断不存在的情况，出现次数=结束位置-开始位置+1。
二分查找
class Solution {
public int countTarget(int[] scores, int target) {
// 二分
int n = scores.length, l = 0, r = n-1;
if(n == 0) return 0;
while(l <= r) {
int mid = l + ((r-l)>>1);
if(scores[mid] < target) l = mid + 1; // 往右逼近 找开始位置
else r = mid - 1;// 若scores[mid]=target会一直往左逼近开始位置,且有start=mid,start=r+1
}
if(r+1 >= n || scores[r+1] != target) return 0;
int start = r+1;// 记录开始位置 且必存在target
l = 0;
r = n-1;
while(l <= r){
int mid = l + ((r-l)>>1);
if(scores[mid] > target) r = mid - 1;
else l = mid + 1; // end = l-1
}
return l-start;//(l-1)-start+1
}
}
复杂度分析
- 时间复杂度：
O(logn)，两次二分查找时间复杂度均为O(logn)，n为数组scores长度。 - 空间复杂度：
O(1)。
2023.1.5
