题目描述

请你实现一个能够支持以下两种方法的推文计数类 TweetCounts：

1. recordTweet(string tweetName, int time)
   • 记录推文发布情况：用户 tweetName 在 time（以 秒 为单位）时刻发布了一条推文。
2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)
   • 返回从开始时间 startTime（以 秒 为单位）到结束时间 endTime（以 秒 为单位）内，每 分 minute，时 hour 或者 日 day（取决于 freq）内指定用户 tweetName 发布的推文总数。
   • freq 的值始终为 分 minute，时 hour 或者 日 day 之一，表示获取指定用户 tweetName 发布推文次数的时间间隔。
   • 第一个时间间隔始终从 startTime 开始，因此时间间隔为 [startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)>，其中 i 和 delta（取决于 freq）都是非负整数。

样例

输入：
["TweetCounts",
 "recordTweet",
 "recordTweet",
 "recordTweet",
 "getTweetCountsPerFrequency",
 "getTweetCountsPerFrequency",
 "recordTweet",
 "getTweetCountsPerFrequency"
]
[[],
 ["tweet3",0],
 ["tweet3",60],
 ["tweet3",10],
 ["minute","tweet3",0,59],
 ["minute","tweet3",0,60],
 ["tweet3",120],
 ["hour","tweet3",0,210]
]

输出：
[null,null,null,null,[2],[2,1],null,[4]]

解释：
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);
// "tweet3" 发布推文的时间分别是 0, 10 和 60 。
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59);
// 返回 [2]。统计频率是每分钟（60 秒），因此只有一个有效时间间隔 [0,60> - > 2 条推文。
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60);
// 返回 [2,1]。统计频率是每分钟（60 秒），因此有两个有效时间间隔 1) [0,60> - > 2 条推文，和 2) [60,61> - > 1 条推文。 
tweetCounts.recordTweet("tweet3", 120);
// "tweet3" 发布推文的时间分别是 0, 10, 60 和 120。
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);
// 返回 [4]。统计频率是每小时（3600 秒），因此只有一个有效时间间隔 [0,211> - > 4 条推文。

限制

• 同时考虑 recordTweet 和 getTweetCountsPerFrequency，最多有 10000 次操作。
• 0 <= time, startTime, endTime <= 10^9
• 0 <= endTime - startTime <= 10^4

算法

(暴力，有序集) 插入 $O(\log n)$，查询 $O(n)$

1. 构建一个字符串到多重集的映射。每次插入时，将新时间插入到对应字符串的多重集中。
2. 查询时，使用内置的 lower_bound 和 upper_bound 找到上下界。由于 C++ 自带的多重集不支持求区间个数的操作，所以只能在上下界中暴力枚举。

时间复杂度

• 插入的时间复杂度为 $O(\log n)$。
• 查询的时间复杂度最坏为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储。

C++ 代码

class TweetCounts {
public:
    unordered_map<string, multiset<int>> tweets;

    TweetCounts() {

    }

    void recordTweet(string tweetName, int time) {
        tweets[tweetName].insert(time);
    }

    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        vector<int> ans;
        int l;

        if (freq == "minute") l = 60;
        else if (freq == "hour") l = 3600;
        else l = 86400;

        ans.resize((endTime - startTime) / l + 1);

        auto it_up = tweets[tweetName].upper_bound(endTime);
        auto it_low = tweets[tweetName].lower_bound(startTime);

        for (; it_low != it_up; it_low++) {
            int x = *it_low;
            ans[(x - startTime) / l]++;
        }

        return ans;
    }
};

/**
 * Your TweetCounts object will be instantiated and called as such:
 * TweetCounts* obj = new TweetCounts();
 * obj->recordTweet(tweetName,time);
 * vector<int> param_2 = obj->getTweetCountsPerFrequency(freq,tweetName,startTime,endTime);
 */