推文计数
难度:
标签:
题目描述
代码结果
运行时间: 80 ms, 内存: 23.4 MB
/*
思路:
1. 创建 TweetCounts 类,其包含记录推文时间的记录。
2. recordTweet 方法用于记录推文的 tweetName 和时间。
3. getTweetCountsPerFrequency 方法根据给定的频率(minute、hour、day)统计指定时间范围内的推文数量。
4. 使用 TreeMap 数据结构存储推文记录,便于按时间排序和查询。
5. 利用 Java Stream API 处理和统计推文数量。
*/
import java.util.*;
import java.util.stream.Collectors;
class TweetCounts {
private Map<String, TreeMap<Integer, Integer>> tweetRecords;
public TweetCounts() {
tweetRecords = new HashMap<>();
}
public void recordTweet(String tweetName, int time) {
tweetRecords.putIfAbsent(tweetName, new TreeMap<>());
TreeMap<Integer, Integer> times = tweetRecords.get(tweetName);
times.put(time, times.getOrDefault(time, 0) + 1);
}
public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
if (!tweetRecords.containsKey(tweetName)) {
return Collections.emptyList();
}
int interval = getInterval(freq);
TreeMap<Integer, Integer> times = tweetRecords.get(tweetName);
return times.subMap(startTime, true, endTime, true).entrySet().stream()
.collect(Collectors.groupingBy(e -> (e.getKey() - startTime) / interval, Collectors.summingInt(Map.Entry::getValue)))
.values().stream()
.collect(Collectors.toList());
}
private int getInterval(String freq) {
switch (freq) {
case "minute": return 60;
case "hour": return 3600;
case "day": return 86400;
default: throw new IllegalArgumentException("Invalid frequency");
}
}
}
解释
方法:
这道题目要求实现一个推文计数类 TweetCounts,需要支持推文记录和按照给定频率统计推文数量的功能。解题思路如下:
1. 使用一个字典 self.tweets 来存储每个推文名称对应的推文发布时间列表。使用 SortedList 来保持时间列表的有序性,便于后续的二分查找。
2. recordTweet 方法直接在对应推文名称的时间列表中添加新的推文时间。
3. getTweetCountsPerFrequency 方法首先确定统计的时间频率,然后利用二分查找找到第一个不小于 startTime 的时间索引。接着,从这个索引开始遍历时间列表,统计每个时间段内的推文数量,直到遍历完所有时间或者到达 endTime。
时间复杂度:
O(logN + M)
空间复杂度:
O(T)