推文计数

标签: 设计哈希表二分查找有序集合排序

难度: 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 对象。
存储记录时间的 tweetName (以秒为单位)。
List<integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) 返回一个整数列表，表示给定时间 [startTime, endTime] （单位秒）和频率频率中，每个 时间块 中带有 tweetName 的 tweet 的数量。
- 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]]

解释：
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 条推文。

提示：

0 <= time, startTime, endTime <= 10⁹
0 <= endTime - startTime <= 10⁴
recordTweet 和 getTweetCountsPerFrequency，最多有 10⁴ 次操作。

Submission

运行时间: 80 ms

内存: 23.4 MB

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]:
        l = self.tweets[tweetName]
        if not l:
            return [0]
        f = 60
        if freq == "hour":
            f = 3600
        elif freq == 'day':
            f = 86400
        i = l.bisect_left(startTime)
        end = min(startTime + f, endTime + 1)
        ans = [0]
        n = len(l)
        while i < n and l[i] <= endTime:
            while end <= l[i]:
                ans.append(0)
                end += f
            ans[-1] += 1
            i += 1
        while end <= endTime:
            ans.append(0)
            end += f

        return ans





# Your TweetCounts object will be instantiated and called as such:
# obj = TweetCounts()
# obj.recordTweet(tweetName,time)
# param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime)

Explain

这道题目要求实现一个推文计数类 TweetCounts，需要支持推文记录和按照给定频率统计推文数量的功能。解题思路如下： 1. 使用一个字典 self.tweets 来存储每个推文名称对应的推文发布时间列表。使用 SortedList 来保持时间列表的有序性，便于后续的二分查找。 2. recordTweet 方法直接在对应推文名称的时间列表中添加新的推文时间。 3. getTweetCountsPerFrequency 方法首先确定统计的时间频率，然后利用二分查找找到第一个不小于 startTime 的时间索引。接着，从这个索引开始遍历时间列表，统计每个时间段内的推文数量，直到遍历完所有时间或者到达 endTime。

时间复杂度: O(logN + M)

空间复杂度: O(T)

from sortedcontainers import SortedList
from collections import defaultdict

class TweetCounts:

    def __init__(self):
        self.tweets = defaultdict(SortedList)  # Initialize a dictionary to store tweet times for each tweet name

    def recordTweet(self, tweetName: str, time: int) -> None:
        self.tweets[tweetName].add(time)  # Add the tweet time to the corresponding tweet name

    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
        l = self.tweets[tweetName]  # Get the list of tweet times for the given tweet name
        if not l:
            return [0]  # If no tweets, return [0]
        f = 60  # Set the default frequency to 60 seconds (1 minute)
        if freq == \"hour\":
            f = 3600  # Set the frequency to 3600 seconds (1 hour) if specified
        elif freq == 'day':
            f = 86400  # Set the frequency to 86400 seconds (1 day) if specified
        i = l.bisect_left(startTime)  # Find the index of the first tweet time not less than startTime
        end = min(startTime + f, endTime + 1)  # Set the end of the first time interval
        ans = [0]  # Initialize the answer list with one interval
        n = len(l)
        while i < n and l[i] <= endTime:  # Iterate through the tweet times within the given time range
            while end <= l[i]:
                ans.append(0)  # Add a new interval if the current tweet time is beyond the current interval
                end += f  # Move to the next interval
            ans[-1] += 1  # Increment the count of tweets in the current interval
            i += 1  # Move to the next tweet time
        while end <= endTime:  # Add empty intervals if there are any remaining intervals within the time range
            ans.append(0)
            end += f
        return ans  # Return the list of tweet counts per interval

# Your TweetCounts object will be instantiated and called as such:
# obj = TweetCounts()
# obj.recordTweet(tweetName,time)
# param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime)