leetcode
leetcode 1251 ~ 1300
推文计数

推文计数

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

相关问题