[LeetCode][LCR172]统计目标成绩的出现次数——二分找边界

题目

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

某班级考试成绩按非严格递增顺序记录于整数数组 scores，请返回目标成绩 target 的出现次数。

• 示例 1：

输入：scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出：3

• 示例 2：

输入：scores = [1, 2, 3, 5, 7, 9], target = 6
输出：0

• 提示：
• 0 <= scores.length <= 105
• -109 <= scores[i] <= 109
• scores 是一个非递减数组
• -109 <= target <= 109

注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

解法1：哈希表直接统计出现次数

class Solution {
public:
    int countTarget(vector<int>& scores, int target) {
        map<int, int> m;
        for(auto &ele:scores) m[ele]++;
        return m[target] ? m[target] : 0;
    }
};

解法2：二分查找边界

1. 如果使用哈希表进行统计，需要遍历整个数组，时间复杂度是 O(n)，且并没有用到数组是非递减序列这个条件
2. 注意到非递减序列，如果目标值在数组中出现，则一定是连续出现的，那么只需要找到其上下边界即可，上下边界的查找可以使用二分法，此时不需要遍历整个序列，时间复杂度小于 O(n)
3. 此处的二分查找为常规二分查找的变形，如果目标节点在序列中，返回的是右开的上界；如果目标节点不在序列中，那么则返回目标节点该有的插入位置，所以如果要找 target 左边的边界，则对 target-1 进行寻找即可
4. 此处的二分查找如何编写，其实就是将常规的二分查找的 nums[middle]==target 合并到 tar>=nums[middle] 这种情况中，随便选一种合并即可

class Solution {
public:
    int findBound(vector<int>& nums, int tar){
        int left=0, right=nums.size()-1;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(tar>=nums[middle]) left=middle+1;
            else right=middle-1;
        }
        return left;
    }
    int countTarget(vector<int>& scores, int target) {
        return findBound(scores, target) - findBound(scores, target-1);
    }
};

解法3：利用 STL 内置的边界查找函数

1. upper_bound() 寻找有序序列大于 target 的第一个最小的元素
2. lower_bound() 寻找有序序列第一个等于 target 的元素

class Solution {
public:
    int countTarget(vector<int>& scores, int target) {
        return upper_bound(scores.begin(), scores.end(), target) - lower_bound(scores.begin(), scores.end(), target);
    }
};