题目描述
思路解析动画文字版
记牢两步:先用「用户 → 分钟集合」的哈希表扫一遍日志,靠 Set 去重求出每人的 UAM;再按每个集合的大小 size,给答案数组 ans[size 减 1] 计票。下面每帧都在套这套。
阶段一 · 日志 + 空的用户集合表：先看清画面。上面一排是 6 条日志,每格写成「用户,分钟」,比如「0,5」表示用户 0 在第 5 分钟操作过。右边这张表现在空着,它会给每个用户挂一个分钟集合。接下来紫色指针从第 0 条日志一格一格往右走,把每条日志的分钟,放进对应用户的集合里,集合会自动去掉重复的分钟。先从第 0 条开始。
第 0 条 · 读日志 (用户 0, 分钟 5)：紫色指针落在第 0 条日志「0,5」,拆开看是用户 0 在第 5 分钟操作。到右边找用户 0 这一行,他现在的分钟集合是 { }。这是用户 0 第一次出现,给他新开一行空集合。
第 0 条 · 分钟 5 入集合：分钟 5 是用户 0 的新分钟,加进集合后变成 { 5 },大小来到 1。这一条处理完,指针会挪到下一格。继续扫。
第 1 条 · 读日志 (用户 1, 分钟 2)：紫色指针落在第 1 条日志「1,2」,拆开看是用户 1 在第 2 分钟操作。到右边找用户 1 这一行,他现在的分钟集合是 { }。这是用户 1 第一次出现,给他新开一行空集合。
第 1 条 · 分钟 2 入集合：分钟 2 是用户 1 的新分钟,加进集合后变成 { 2 },大小来到 1。这一条处理完,指针会挪到下一格。继续扫。
第 2 条 · 读日志 (用户 0, 分钟 2)：紫色指针落在第 2 条日志「0,2」,拆开看是用户 0 在第 2 分钟操作。到右边找用户 0 这一行,他现在的分钟集合是 { 5 }。这行被点亮,准备把分钟 2 加进去。
第 2 条 · 分钟 2 入集合：分钟 2 是用户 0 的新分钟,加进集合后变成 { 5, 2 },大小来到 2。这一条处理完,指针会挪到下一格。继续扫。
第 3 条 · 读日志 (用户 2, 分钟 4)：紫色指针落在第 3 条日志「2,4」,拆开看是用户 2 在第 4 分钟操作。到右边找用户 2 这一行,他现在的分钟集合是 { }。这是用户 2 第一次出现,给他新开一行空集合。
第 3 条 · 分钟 4 入集合：分钟 4 是用户 2 的新分钟,加进集合后变成 { 4 },大小来到 1。这一条处理完,指针会挪到下一格。继续扫。
第 4 条 · 读日志 (用户 0, 分钟 5)：紫色指针落在第 4 条日志「0,5」,拆开看是用户 0 在第 5 分钟操作。到右边找用户 0 这一行,他现在的分钟集合是 { 5, 2 }。这行被点亮,准备把分钟 5 加进去。
第 4 条 · 分钟 5 重复,去重：注意这一条:分钟 5 早就在用户 0 的集合里了。Set 会把这次重复直接吞掉,集合还是 { 5, 2 },大小没变,仍是 2。这正是「同一分钟做几次也只算一次」的关键,活跃分钟数看的是不同分钟的个数。看下一条。
第 5 条 · 读日志 (用户 1, 分钟 3)：紫色指针落在第 5 条日志「1,3」,拆开看是用户 1 在第 3 分钟操作。到右边找用户 1 这一行,他现在的分钟集合是 { 2 }。这行被点亮,准备把分钟 3 加进去。
第 5 条 · 分钟 3 入集合：分钟 3 是用户 1 的新分钟,加进集合后变成 { 2, 3 },大小来到 2。这一条处理完,指针会挪到下一格。
阶段一完成 · 三个集合就绪：6 条日志全部扫完,三个集合定型:用户 0 是 { 5, 2 },大小 2;用户 1 是 { 2, 3 },大小 2;用户 2 是 { 4 },大小 1。每个集合的大小,就是这个用户的活跃分钟数 UAM。注意用户 0 那条日志里 5 出现了两次,靠去重最后只留一个,UAM 才是 2 而不是 3。接下来进入第二步:按这三个大小去计票。
阶段二 · 答案数组 [0,0,0]：现在换成答案数组登场,它长度是 k = 3,三格从左到右分别代表 UAM 等于 1、2、3 的用户数,一开始都是 0。右边这张表把三个用户的集合大小列出来当参照。接下来一个个用户看:他的集合多大,就给答案里对应那格加一票。要留意题目下标从 1 开始,而数组从 0 开始,所以 UAM 为 size 的用户,票落在第 size 减 1 这一格。
用户 0 · UAM = 2：轮到用户 0,他的集合大小是 2,也就是 UAM 等于 2。那就该往答案里「UAM 等于 2」的那格投一票,这格的数组下标是 2 减 1 等于 1,紫色指针停在这里,它现在的值是 0。
用户 0 · 计票 ans[1] = 1：给这格加一票:第 1 格从 0 变成 1,意思是 UAM 等于 2 的用户现在数到了 1 个。换下一个用户。
用户 1 · UAM = 2：轮到用户 1,他的集合大小是 2,也就是 UAM 等于 2。那就该往答案里「UAM 等于 2」的那格投一票,这格的数组下标是 2 减 1 等于 1,紫色指针停在这里,它现在的值是 1。
用户 1 · 计票 ans[1] = 2：给这格加一票:第 1 格从 1 变成 2,意思是 UAM 等于 2 的用户现在数到了 2 个。换下一个用户。
用户 2 · UAM = 1：轮到用户 2,他的集合大小是 1,也就是 UAM 等于 1。那就该往答案里「UAM 等于 1」的那格投一票,这格的数组下标是 1 减 1 等于 0,紫色指针停在这里,它现在的值是 0。
用户 2 · 计票 ans[0] = 1：给这格加一票:第 0 格从 0 变成 1,意思是 UAM 等于 1 的用户现在数到了 1 个。三个用户都投完了。
完成 · 答案 = [1, 2, 0]：三个用户都投完票,回看一遍:用户 2 的 UAM 是 1,让第 1 格得 1 票;用户 0 和用户 1 的 UAM 都是 2,让第 2 格得 2 票;没有人 UAM 是 3,第 3 格是 0。所以答案数组是 [1, 2, 0],和题面对得上。整道题就两步:先用「用户到分钟集合」的哈希表去重求出每人 UAM,再按集合大小往答案数组计票。用户投票的先后顺序不影响结果,换个顺序数,答案一样。
边界:单条日志得 [1];同一用户重复分钟去重后 UAM 变小([0,0,1,0,0] 而非算成 5);k 比最大 UAM 大时,尾部自然补 0。
面试重点:用 Set 存分钟天然去重求 UAM;计票的 size 减 1 是下标从 1 到从 0 的桥梁;三语言差别在自动新建空集合的写法(defaultdict / 中括号默认构造 / computeIfAbsent)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]: d = defaultdict(set) for i, t in logs: d[i].add(t) ans = [0] * k for ts in d.values(): ans[len(ts) - 1] += 1 return ans复杂度
- 时间：O(n + m)，n 是日志条数,m 是 k(答案数组长度)。第一步扫全部 n 条日志,每条做一次集合插入,哈希集合的插入平均是常数,所以是 O(n);第二步遍历所有用户的集合、逐个计票,总的插入元素个数不超过 n,加上开长度 k 的数组,合起来 O(n + k)。整体线性,和暴力两两比日志的 O(n 的平方) 不是一个量级
- 空间：O(u + d + k)，按峰值算。哈希表存 u 个用户,所有用户的分钟集合合起来最多存 d 个「用户加分钟」去重对,d 不超过日志条数 n;答案数组占 k。三部分相加,最坏就是 O(n + k)。这里只额外存集合和计票数组,不存日志本身的副本
易错点
面试追问把动画讲成自己的话
追问为什么每个用户要用集合 Set 而不是列表来存分钟?
追问计票时那个减 1 是怎么来的,能省掉吗?
追问三种语言在建集合上有什么细节差别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
连接后等于目标字符串的字符串对
LeetCode 2023 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题