1348. 推文计数器（按频率统计）

Medium

题目描述

一家社交媒体公司正在尝试通过分析在特定时间段内发生的推文数量来监控其网站上的活动。这些时间段可以根据特定的频率（每分钟、每小时或每天）分割成更小的时间块。

例如，时间段 [10, 10000]（以秒为单位）将根据以下频率分割为以下时间块：

每分钟（60 秒块）：[10,69], [70,129], [130,189], …, [9970,10000]
每小时（3600 秒块）：[10,3609], [3610,7209], [7210,10000]
每天（86400 秒块）：[10,10000]

请注意，最后一个块可能比指定频率的块大小短，并且将始终以时间段的结束时间结束（在上面的示例中为 10000）。

设计并实现一个 API 来帮助公司进行分析。

实现 TweetCounts 类：

TweetCounts() 初始化 TweetCounts 对象。
void recordTweet(String tweetName, int time) 在记录的时间（以秒为单位）存储 tweetName。
List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) 返回一个整数列表，表示在给定时间段 [startTime, endTime]（以秒为单位）和频率 freq 下，每个时间块中具有 tweetName 的推文数量。
- freq 是 “minute”、“hour” 或 “day” 之一，分别表示每分钟、每小时或每天的频率。

示例：

输入
["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]]

约束条件：

0 <= time, startTime, endTime <= 10^9
0 <= endTime - startTime <= 10^4
recordTweet 和 getTweetCountsPerFrequency 的总调用次数不超过 10^4。

解题思路

这道题是一个系统设计题，需要实现一个推文计数系统。核心思路如下：

数据结构选择： 使用哈希表存储每个推文名称对应的时间戳列表。为了在查询时能够高效地找到指定时间范围内的推文，需要保持时间戳的有序性。

记录推文： 对于每个推文名称，维护一个有序的时间戳列表。当记录新推文时，将时间戳插入到对应的列表中并保持有序。

统计推文频率：

根据频率类型确定时间块大小：minute对应60秒，hour对应3600秒，day对应86400秒
计算在[startTime, endTime]范围内需要多少个完整的时间块
对于每个时间块，使用二分搜索在有序时间戳列表中找到该时间块内的推文数量
最后一个时间块可能不完整，需要特殊处理

优化技巧：

使用二分搜索（lower_bound和upper_bound）来快速定位时间范围
保持时间戳列表的有序性，插入时可能需要排序或使用插入排序
对于频繁查询的场景，可以考虑使用更复杂的数据结构如平衡二叉搜索树

这种方法的优势是查询效率高，特别适合读多写少的场景。

代码实现

class TweetCounts {
private:
    unordered_map<string, vector<int>> tweets;
    
public:
    TweetCounts() {
        
    }
    
    void recordTweet(string tweetName, int time) {
        tweets[tweetName].push_back(time);
        sort(tweets[tweetName].begin(), tweets[tweetName].end());
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int interval;
        if (freq == "minute") interval = 60;
        else if (freq == "hour") interval = 3600;
        else interval = 86400;
        
        vector<int> result;
        if (tweets.find(tweetName) == tweets.end()) {
            int chunks = (endTime - startTime) / interval + 1;
            return vector<int>(chunks, 0);
        }
        
        vector<int>& times = tweets[tweetName];
        
        for (int start = startTime; start <= endTime; start += interval) {
            int end = min(start + interval - 1, endTime);
            
            auto left = lower_bound(times.begin(), times.end(), start);
            auto right = upper_bound(times.begin(), times.end(), end);
            
            result.push_back(right - left);
        }
        
        return result;
    }
};

class TweetCounts:

    def __init__(self):
        self.tweets = {}

    def recordTweet(self, tweetName: str, time: int) -> None:
        if tweetName not in self.tweets:
            self.tweets[tweetName] = []
        self.tweets[tweetName].append(time)
        self.tweets[tweetName].sort()

    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
        interval = {"minute": 60, "hour": 3600, "day": 86400}[freq]
        
        result = []
        if tweetName not in self.tweets:
            chunks = (endTime - startTime) // interval + 1
            return [0] * chunks
        
        times = self.tweets[tweetName]
        
        start = startTime
        while start <= endTime:
            end = min(start + interval - 1, endTime)
            
            left = bisect.bisect_left(times, start)
            right = bisect.bisect_right(times, end)
            
            result.append(right - left)
            start += interval
        
        return result

public class TweetCounts {
    private Dictionary<string, List<int>> tweets;

    public TweetCounts() {
        tweets = new Dictionary<string, List<int>>();
    }
    
    public void RecordTweet(string tweetName, int time) {
        if (!tweets.ContainsKey(tweetName)) {
            tweets[tweetName] = new List<int>();
        }
        tweets[tweetName].Add(time);
        tweets[tweetName].Sort();
    }
    
    public IList<int> GetTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int interval = freq == "minute" ? 60 : freq == "hour" ? 3600 : 86400;
        
        List<int> result = new List<int>();
        if (!tweets.ContainsKey(tweetName)) {
            int chunks = (endTime - startTime) / interval + 1;
            for (int i = 0; i < chunks; i++) {
                result.Add(0);
            }
            return result;
        }
        
        List<int> times = tweets[tweetName];
        
        for (int start = startTime; start <= endTime; start += interval) {
            int end = Math.Min(start + interval - 1, endTime);
            
            int left = BinarySearchLeft(times, start);
            int right = BinarySearchRight(times, end);
            
            result.Add(right - left);
        }
        
        return result;
    }
    
    private int BinarySearchLeft(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int BinarySearchRight(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var TweetCounts = function() {
    this.tweets = new Map();
};

TweetCounts.prototype.recordTweet = function(tweetName, time) {
    if (!this.tweets.has(tweetName)) {
        this.tweets.set(tweetName, []);
    }
    this.tweets.get(tweetName).push(time);
    this.tweets.get(tweetName).sort((a, b) => a - b);
};

TweetCounts.prototype.getTweetCountsPerFrequency = function(freq, tweetName, startTime, endTime) {
    const intervals = {"minute": 60, "hour": 3600, "day": 86400};
    const interval = intervals[freq];
    
    const result = [];
    if (!this.tweets.has(tweetName)) {
        const chunks = Math.floor((endTime - startTime) / interval) + 1;
        return new Array(chunks).fill(0);
    }
    
    const times = this.tweets.get(tweetName);
    
    for (let start = startTime; start <= endTime; start += interval) {
        const end = Math.min(start + interval - 1, endTime);
        
        const left = this.binarySearchLeft(times, start);
        const right = this.binarySearchRight(times, end);
        
        result.push(right - left);
    }
    
    return result;
};

TweetCounts.prototype.binarySearchLeft = function(arr, target) {
    let left = 0, right = arr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

TweetCounts.prototype.binarySearchRight = function(arr, target) {
    let left = 0, right = arr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
recordTweet	O(n log n)	O(n)
getTweetCountsPerFrequency	O(k log n)	O(k)

其中：

n 是某个推文名称的时间戳数量
k 是查询时间范围内的时间块数量
recordTweet 需要排序，所以是 O(n log n)
getTweetCountsPerFrequency 中每个时间块需要进行两次二分搜索，总共 k 个时间块

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目