• 难度：Medium
• 题目链接：https://leetcode-cn.com/problems/rank-from-stream-lcci/

题目描述

来源于 https://leetcode-cn.com/

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

实现 track(int x) 方法，每读入一个数字都会调用该方法；

实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

注意：本题相对原题稍作改动

示例:

输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

提示：

• x <= 50000
• track 和 getRankOfNumber 方法的调用次数均不超过 2000 次

解法：

用平衡树来作为计数器，计算秩的时候累加键值小于 x 的节点的 val 即可。

class StreamRank {
public:
    StreamRank() {}

    void track(int x) {
        counter[x]++;
    }

    int getRankOfNumber(int x) {
        int num = 0;
        for(auto & it : counter){
            if(it.first > x){
                break;
            }
            num += it.second;
        }
        return num;
    }

private:
    map<int, int> counter;
};