LeetCode 1348：推文时间序列统计的设计与优化

1. 问题背景与需求分析Tweet Counts Per Frequency 是 LeetCode 平台上的一道中等难度设计题属于系统设计类别。这道题模拟了社交媒体平台中常见的推文统计功能要求实现一个能够按不同时间粒度统计推文数量的类。在实际应用中类似功能广泛存在于各类社交平台微博的热搜统计Twitter 的话题趋势分析论坛的活跃度监控题目核心是设计一个 TweetCounts 类需要支持两种操作recordTweet(string tweetName, int time) - 记录推文getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) - 获取统计结果2. 数据结构选型与设计思路2.1 存储结构的选择对于这类时间序列数据的统计问题常见的数据结构选择有有序数组优点查询时可以二分查找插入需要维护有序性缺点插入时间复杂度 O(n)平衡二叉搜索树优点插入和查询都是 O(logn)缺点实现复杂哈希表列表优点插入快查询时需要排序缺点查询性能不稳定经过比较我们选择使用哈希表有序列表的组合from bisect import bisect_left, insort class TweetCounts: def __init__(self): self.tweets defaultdict(list)2.2 时间粒度处理题目中定义了三种统计频率minute每分钟hour每小时day每天需要将时间戳转换为对应的时间区间。这里的关键是正确计算时间段的划分方式。3. 核心算法实现3.1 记录推文实现def recordTweet(self, tweetName: str, time: int) - None: insort(self.tweets[tweetName], time)使用 bisect 模块的 insort 方法可以在插入时自动维护列表的有序性保证后续查询效率。3.2 统计查询实现def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) - List[int]: if tweetName not in self.tweets: return [] delta 60 if freq minute else 3600 if freq hour else 86400 times self.tweets[tweetName] res [] i startTime while i endTime: j min(i delta, endTime 1) left bisect_left(times, i) right bisect_left(times, j) res.append(right - left) i j return res算法步骤解析确定时间间隔 delta初始化结果列表和起始时间指针 i循环处理每个时间段计算当前时间段的结束时间 j使用二分查找确定时间段内的推文数量移动指针到下一个时间段4. 复杂度分析与优化4.1 时间复杂度recordTweet: O(n) 由于需要移动元素getTweetCountsPerFrequency: O(mlogn) m是时间段数量4.2 优化思路对于高频插入场景可以考虑改用平衡二叉搜索树结构如 Python 中的 SortedContainer 模块from sortedcontainers import SortedList class TweetCounts: def __init__(self): self.tweets defaultdict(SortedList) def recordTweet(self, tweetName: str, time: int) - None: self.tweets[tweetName].add(time) def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) - List[int]: if tweetName not in self.tweets: return [] delta 60 if freq minute else 3600 if freq hour else 86400 times self.tweets[tweetName] res [] i startTime while i endTime: j min(i delta, endTime 1) left times.bisect_left(i) right times.bisect_left(j) res.append(right - left) i j return res这样可以将 recordTweet 的时间复杂度优化到 O(logn)。5. 边界条件与测试用例5.1 常见边界情况重复时间戳的记录startTime 等于 endTime查询不存在的 tweetName大时间跨度的统计5.2 测试用例示例def test_tweet_counts(): tc TweetCounts() tc.recordTweet(tweet1, 0) tc.recordTweet(tweet1, 60) tc.recordTweet(tweet1, 10) assert tc.getTweetCountsPerFrequency(minute, tweet1, 0, 59) [2] assert tc.getTweetCountsPerFrequency(minute, tweet1, 0, 60) [2, 1] assert tc.getTweetCountsPerFrequency(hour, tweet1, 0, 3600) [3] assert tc.getTweetCountsPerFrequency(day, notexist, 0, 100) []6. 实际应用扩展6.1 分布式场景下的实现对于大型社交平台推文数据量巨大需要考虑分布式方案按 tweetName 分片存储使用 MapReduce 进行统计计算预聚合常用时间粒度的统计数据6.2 实时统计优化可以使用以下技术优化实时查询性能时间序列数据库如 InfluxDB流处理框架如 Flink近似统计算法如 HyperLogLog7. 同类问题对比类似的时间序列统计问题在 LeetCode 上还有Data Stream as Disjoint IntervalsRange ModuleMy Calendar III这些题目都涉及对时间区间的操作和统计可以对比学习。