[LeetCode] 1348. Tweet Counts Per Frequency 推文计数

A social media company is trying to monitor activity on their site by analyzing the number of tweets that occur in select periods of time. These periods can be partitioned into smaller time chunks based on a certain frequency (every minute, hour, or day).

For example, the period [10, 10000] (in seconds) would be partitioned into the following time chunks with these frequencies:

• Every minute (60-second chunks): [10,69], [70,129], [130,189], ..., [9970,10000]
• Every hour (3600-second chunks): [10,3609], [3610,7209], [7210,10000]
• Every day (86400-second chunks): [10,10000]

Notice that the last chunk may be shorter than the specified frequency's chunk size and will always end with the end time of the period (10000 in the above example).

Design and implement an API to help the company with their analysis.

Implement the TweetCounts class:

• TweetCounts() Initializes the TweetCounts object.
• void recordTweet(String tweetName, int time) Stores the tweetName at the recorded time (in seconds).
• List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) Returns a list of integers representing the number of tweets with tweetName in each time chunk for the given period of time [startTime, endTime] (in seconds) and frequency freq.
  • freq is one of "minute", "hour", or "day" representing a frequency of every minute, hour, or day respectively.

Example:

Input
["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]]

Output
[null,null,null,null,[2],[2,1],null,[4]]

Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0); // New tweet "tweet3" at time 0
tweetCounts.recordTweet("tweet3", 60); // New tweet "tweet3" at time 60
tweetCounts.recordTweet("tweet3", 10); // New tweet "tweet3" at time 10
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]; chunk [0,59] had 2 tweets
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2,1]; chunk [0,59] had 2 tweets, chunk [60,60] had 1 tweet
tweetCounts.recordTweet("tweet3", 120); // New tweet "tweet3" at time 120
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210); // return [4]; chunk [0,210] had 4 tweets

Constraints:

• 0 <= time, startTime, endTime <= 109
• 0 <= endTime - startTime <= 104
• There will be at most 104 calls in total to recordTweet and getTweetCountsPerFrequency.

这道题让统计特定时间段内推特的个数，有两个主要的函数需要实现，一个是 recordTweet，即记录下每次发某个推特的时间，这里的 tweetName 应该可以看作推特的话题，比如 HashTag 什么的，因为一般来说不会大量的发送完全相同的推特。另一个函数 getTweetCountsPerFrequency，让找出给定的起始和终止时间内，每分钟，或每小时，或每天发送某个话题的推特的个数。第一个函数比较容易实现，就是用一个数据结构记录下所有发送的推特，这里需要按照话题归类，因为最终也是按话题来找频率的，所以这里可以用一个 HashMap，来建立推特话题和所有该话题推特发出时间的集合之间的映射。这个集合到底是用 vector 呢，还是用可以自动排序的 HashSet 呢？

博主开始是纠结了一阵的，因为调用 recordTweet 时推特的时间可能是无序的，所以用 vector 的话得到的时间也就是无序的。要不要保留顺序取决于第二个函数该如何实现，给定了起始和结束时间，还有统计频率，分钟，小时或者天，那么就可以知道该时间段需要被分成多少个区间，就用结束时间减去起始时间，再除以频率，然后加1即可。关键是怎么统计每个区间内推特的个数，博主开始的想法是用二分查找，首先查找第一个不小于 startTime 的推特，然后再查找第一个不大于 startTime + freq 的推特，然后查找第一个不大于 startTime + 2*freq 的推特，以此类推，这种方法不但麻烦，而且容易出错。其实并不需要用二分查找，只需要遍历所有的推特，找出在大于等于起始时间，小于等于终止时间，然后计算其所在的区间序号，通过用当前时间减去起始时间，并除以频率即可，然后对应的区间里的次数加1即可，这种方法既简单又高效，参见代码如下：

class TweetCounts {
public:
    TweetCounts() {}
    
    void recordTweet(string tweetName, int time) {
        m[tweetName].push_back(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {      
        int n = (endTime - startTime) / freqMap[freq] + 1;
        vector<int> res(n);
        for (int time : m[tweetName]) {
            if (time >= startTime && time <= endTime) {
                int idx = (time - startTime) / freqMap[freq];
                ++res[idx];
            }          
        }
        return res;
    }

private:
    unordered_map<string, vector<int>> m;
    unordered_map<string, int> freqMap{{"minute", 60}, {"hour", 3600}, {"day", 86400}};
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1348

类似题目：

Design Video Sharing Platform

参考资料：

https://leetcode.com/problems/tweet-counts-per-frequency/

https://leetcode.com/problems/tweet-counts-per-frequency/solutions/504456/c-accepted-solution-with-map/

https://leetcode.com/problems/tweet-counts-per-frequency/solutions/503453/java-treemap-accepted-solution-easy-understand/

LeetCode All in One 题目讲解汇总(持续更新中...)