深入剖析 LeetCode 用户活跃分钟数统计问题
一、题目详情
给定用户在 LeetCode 的操作日志，日志以二维整数数组logs表示，其中每个logs[i]=[IDi, timei]，意味着 ID 为IDi的用户在timei分钟时执行了某个操作。多个用户能够同时执行操作，并且单个用户在同一分钟内可以执行多个操作。
用户活跃分钟数（user active minutes，UAM），指用户对 LeetCode 执行操作的唯一分钟数，即便一分钟内执行多个操作，也仅按一分钟计数。
题目要求统计用户活跃分钟数的分布情况，需返回一个长度为k且下标从 1 开始计数的数组answer。对于每个j（1 <= j <= k），answer[j]表示用户活跃分钟数等于j的用户数 。
示例情况
假如logs = [[0,5],[1,2],[0,2],[0,5],[1,3]]，k = 5。用户0在第2和第5分钟执行了操作，活跃分钟数为2；用户1在第2和第3分钟执行了操作，活跃分钟数为2。因此，答案数组中answer[2]应该为2，其他位置为0 。
二、解题思路探索
核心思路
- 记录用户活跃分钟：借助哈希表记录每个用户的活跃分钟。遍历操作日志，将每个用户的操作时间放入对应的哈希表集合中，利用集合自动去重的特性，获取每个用户的唯一活跃分钟。
- 统计活跃分钟分布：遍历哈希表中每个用户的活跃分钟集合，统计集合大小，该大小即为用户的活跃分钟数。依据活跃分钟数，将用户数计入结果数组
answer的对应位置。
思路解析
- 为何使用哈希表：哈希表能够快速地将用户 ID 与他们的活跃分钟集合进行关联，方便我们对每个用户的操作时间进行管理。由于哈希表查找、插入操作的平均时间复杂度为 O (1)，大大提高了算法效率。
- 特殊情况考量：因为题目规定了结果数组
answer的长度为k，在统计活跃分钟数对应的用户数时，需要确保活跃分钟数不超过k，避免数组越界。
三、代码实现展示
Java 代码
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;class Solution {public int[] findingUsersActiveMinutes(int[][] logs, int k) {// 存储每个用户的活跃分钟集合Map<Integer, Set<Integer>> userActiveMinutes = new HashMap<>();// 遍历日志，将每个用户的活跃分钟添加到对应的集合中for (int[] log : logs) {int userId = log[0];int time = log[1];userActiveMinutes.computeIfAbsent(userId, key -> new HashSet<>()).add(time);}// 用于存储用户活跃分钟数的分布情况int[] answer = new int[k];// 遍历每个用户的活跃分钟集合，统计每个活跃分钟数对应的用户数for (Set<Integer> activeMinutes : userActiveMinutes.values()) {int activeCount = activeMinutes.size();if (activeCount <= k) {answer[activeCount - 1]++;}}return answer;}
}
代码说明
- 记录活跃分钟：创建一个
Map<Integer, Set<Integer>>类型的userActiveMinutes哈希表，其中键为用户 ID，值为该用户的活跃分钟集合。遍历操作日志logs，使用computeIfAbsent方法确保每个用户都有对应的活跃分钟集合，并将操作时间添加到集合中。 - 初始化结果数组：创建长度为
k的answer数组，用于存储用户活跃分钟数的分布情况。 - 统计分布情况：遍历
userActiveMinutes中的每个活跃分钟集合，获取集合大小，即用户的活跃分钟数。若活跃分钟数不超过k，则将answer数组对应位置的计数加 1。
四、测试用例验证
测试代码
public class Main {public static void main(String[] args) {Solution solution = new Solution();int[][] logs = {{0,5},{1,2},{0,2},{0,5},{1,3}};int k = 5;int[] result = solution.findingUsersActiveMinutes(logs, k);for (int i : result) {System.out.print(i + " ");}}
}
测试结果分析
上述测试用例中，用户0的活跃分钟数为2，用户1的活跃分钟数也为2。运行程序后，输出结果answer[2 - 1]处为2，符合预期。
五、总结与拓展
总结
这道题通过巧妙运用哈希表和集合，解决了用户活跃分钟数的统计和分布问题。算法的时间复杂度为 O (n)，其中 n 为操作日志的长度，因为主要操作是对操作日志进行一次遍历。空间复杂度为 O (n + k)，哈希表存储用户活跃分钟信息的空间复杂度为 O (n)，结果数组占用空间为 O (k)。
拓展思考
- 数据规模变化：当操作日志数据量非常大时，内存占用可能成为问题。可以考虑分块处理数据，减少单次处理的数据量。
- 多语言实现差异：在不同编程语言中，哈希表和集合的实现细节和性能有所不同。例如，Python 中的
defaultdict和set，在解决这类问题时，代码风格和性能表现会与 Java 有所差异。 - 类似问题：像统计用户登录天数分布、网站用户访问页面的频次分布等问题，都可以采用类似的思路解决。