1348-推文计数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

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

例如，周期 [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 <= 109
  • 0 <= endTime - startTime <= 104
  • recordTweet 和 getTweetCountsPerFrequency，最多有 104 次操作。

方法一：线性表暴力

使用字典保存用户，按照用户名使用线性表存储其相应的所有推文，查询时遍历该用户的所有推文判断是否在要求的时间区间内。

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TweetCounts:

    def __init__(self):
        self.user = collections.defaultdict(list)

    def recordTweet(self, tweetName: str, time: int) -> None:
        self.user[tweetName].append(time)

    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
        endTime += 1
        if freq == 'minute':
            length = 60
        elif freq == 'hour':
            length = 60 * 60
        else:
            length = 60 * 60 * 24
        ans = [0] * ((endTime - startTime - 1) // length + 1)
        for t in self.user[tweetName]:
            if endTime > t >= startTime:
                ans[(t - startTime) // length] += 1
        return ans
[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class TweetCounts {
    map<string, vector<int>> user;
public:
    TweetCounts() {
    }
    
    void recordTweet(string tweetName, int time) {
        user[tweetName].push_back(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        endTime += 1;
        int length = 0;
        if (freq == "minute")
            length = 60;
        else if (freq == "hour")
            length = 60 * 60;
        else
            length = 60 * 60 * 24;
        vector<int> ans((endTime - startTime - 1) / length + 1);
        for (int time : user[tweetName])
            if (time >= startTime && time < endTime)
                ++ans[(time - startTime) / length];
        return ans;
    }
};
复杂度分析：

记插入操作的次数为 n，查询操作的次数为 q，查询的时间范围为 t。

  • 时间复杂度：O(q(t+n)) （python），或者 O(q(t+n)+nlogn) （C++）
    • 共有 n 次插入。每次插入需要查询一次用户 ID，python 中的 dict 使用哈希表实现，插入的时间复杂度为 O(1)，C++ 中的 map 使用红黑树实现，插入的时间复杂度为 O(logn)。
    • 共有 q 次查询。每次查询需要进行一次 O(n) 的遍历，时间复杂度为 O(nq)。每次查询还需要建立大小为 O(t) 的数组，时间复杂度为 O(tq)。
    • 综合起来，python 的时间复杂度为 O(q(t+n))，C++ 的时间复杂度为 O(q(t+n)+nlogn)。
  • 空间复杂度：O(n+t)
    • 最多需要存储 n 个用户以及 n 条推文时间，空间复杂度为 O(n)。
    • 查询时需要开辟 O(t) 的数组，空间复杂度为 O(t)。
    • 综合起来，空间复杂度为 O(n+t)。

方法二：平衡二叉树

可以将每个用户的推文时间存储方式换成更有效的平衡二叉树。与暴力法所使用的线性表相比，平衡二叉树保证其中的元素使用二叉树有序排列，其时间复杂度与线性表的区别为：

  • 对于插入操作，线性表的时间复杂度为 O(1)，平衡二叉树的时间复杂度为 O(logn)。
  • 对于查询操作，线性表的时间复杂度为 O(n)，平衡二叉树的时间复杂度为 O(logn)。
    使用平衡二叉树，在查询时只要先在对应用户的所有推文中查询时间范围的上下界，然后在上下界范围内遍历推文发布时间即可。
[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class TweetCounts {
    map<string, set<int>> user;
public:
    TweetCounts() {
    }
    
    void recordTweet(string tweetName, int time) {
        user[tweetName].insert(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int length = 0;
        if (freq == "minute")
            length = 60;
        else if (freq == "hour")
            length = 60 * 60;
        else
            length = 60 * 60 * 24;
        vector<int> ans((endTime - startTime) / length + 1);
        auto begin = user[tweetName].lower_bound(startTime);
        auto end = user[tweetName].upper_bound(endTime);
        for (; begin != end; ++begin) {
            ++ans[(*begin - startTime) / length];
        }
        return ans;
    }
};
复杂度分析：

记插入操作的次数为 n，查询操作的次数为 q，查询的时间范围为 t。

  • 时间复杂度：O(q(t+logn)+nlogn)
    • 共有 n 次插入。每次插入的时间复杂度为 O(logn)。总的插入时间复杂度为 O(nlogn)。
    • 共有 q 次查询。每次查询需要对上下界进行一次 O(logn) 的查询，时间复杂度为 O(qlogn)。每次查询还需要建立大小为 O(t) 的数组，时间复杂度为 O(tq)。
    • 综合起来，时间复杂度为 O(q(t+logn)+nlogn)
  • 空间复杂度：O(n+t)
    • 最多需要存储 n 个用户以及 n 条推文时间，空间复杂度为 O(n)。
    • 查询时需要开辟 O(t) 的数组，空间复杂度为 O(t)。综合起来，空间复杂度为 O(n+t)。
 Comments
On this page
1348-推文计数