Question

1348. 推文计数

English Version

题目描述

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

 

例如，周期 [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 次操作。

解法

方法一：哈希表 + 有序列表

我们用哈希表 data 记录每个用户的推文时间，用有序列表记录每个用户的所有推文时间。

对于 recordTweet 操作，我们将推文时间加入到用户的推文时间列表中。

对于 getTweetCountsPerFrequency 操作，我们先计算出时间间隔 f，然后遍历用户的推文时间列表，统计每个时间间隔内的推文数量。

时间复杂度，对于 recordTweet 操作，总的时间复杂度 $O(n \times \log n)$；对于 getTweetCountsPerFrequency 操作，总的时间复杂度 $O(q \times (t + \log n))$。其中 $n$, $q$ 和 $t$ 分别表示插入的推文数量，查询的次数和时间间隔的长度。

from sortedcontainers import SortedList


class TweetCounts:
  def __init__(self):
    self.d = {"minute": 60, "hour": 3600, "day": 86400}
    self.data = defaultdict(SortedList)

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

  def getTweetCountsPerFrequency(
    self, freq: str, tweetName: str, startTime: int, endTime: int
  ) -> List[int]:
    f = self.d[freq]
    tweets = self.data[tweetName]
    t = startTime
    ans = []
    while t <= endTime:
      l = tweets.bisect_left(t)
      r = tweets.bisect_left(min(t + f, endTime + 1))
      ans.append(r - l)
      t += 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)

class TweetCounts {
  private Map<String, TreeMap<Integer, Integer>> data = new HashMap<>();

  public TweetCounts() {
  }

  public void recordTweet(String tweetName, int time) {
    data.putIfAbsent(tweetName, new TreeMap<>());
    var tm = data.get(tweetName);
    tm.put(time, tm.getOrDefault(time, 0) + 1);
  }

  public List<Integer> getTweetCountsPerFrequency(
    String freq, String tweetName, int startTime, int endTime) {
    int f = 60;
    if ("hour".equals(freq)) {
      f = 3600;
    } else if ("day".equals(freq)) {
      f = 86400;
    }
    var tm = data.get(tweetName);
    List<Integer> ans = new ArrayList<>();
    for (int i = startTime; i <= endTime; i += f) {
      int s = 0;
      int end = Math.min(i + f, endTime + 1);
      for (int v : tm.subMap(i, end).values()) {
        s += v;
      }
      ans.add(s);
    }
    return ans;
  }
}

/**
 * Your TweetCounts object will be instantiated and called as such:
 * TweetCounts obj = new TweetCounts();
 * obj.recordTweet(tweetName,time);
 * List<Integer> param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime);
 */

class TweetCounts {
public:
  TweetCounts() {
  }

  void recordTweet(string tweetName, int time) {
    data[tweetName].insert(time);
  }

  vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
    int f = 60;
    if (freq == "hour")
      f = 3600;
    else if (freq == "day")
      f = 86400;
    vector<int> ans((endTime - startTime) / f + 1);
    auto l = data[tweetName].lower_bound(startTime);
    auto r = data[tweetName].upper_bound(endTime);
    for (; l != r; ++l) {
      ++ans[(*l - startTime) / f];
    }
    return ans;
  }

private:
  unordered_map<string, multiset<int>> data;
};

/**
 * Your TweetCounts object will be instantiated and called as such:
 * TweetCounts* obj = new TweetCounts();
 * obj->recordTweet(tweetName,time);
 * vector<int> param_2 = obj->getTweetCountsPerFrequency(freq,tweetName,startTime,endTime);
 */