LCR 172. 统计目标成绩的出现次数

即使输掉了一切，也不要输掉微笑。

题目

参考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