查找用户活跃分钟数 图解题解
这道题到底在问什么
- 输入
- logs=[[0,5],[1,2],[0,2],[2,4],[0,5],[1,3]], k=3
- 输出
- [1,2,0]
- 输入
- logs=[[1,1],[2,2],[2,3]], k=4
- 输出
- [1,1,0,0]
- 输入
- logs=[[0,4],[0,1],[0,1],[0,4],[0,2]], k=5
- 输出
- [0,0,1,0,0]
最优解：一步一步想明白
- 3记牢两步:先用「用户 → 分钟集合」的哈希表扫一遍日志,靠 Set 去重求出每人的 UAM;再按每个集合的大小 size,给答案数组 ans[size 减 1] 计票。下面每帧都在套这套。
- 4先看清画面。上面一排是 6 条日志,每格写成「用户,分钟」,比如「0,5」表示用户 0 在第 5 分钟操作过。右边这张表现在空着,它会给每个用户挂一个分钟集合。接下来紫色指针从第 0 条日志一格一格往右走,把每条日志的分钟,放进对应用户的集合里,集合会自动去掉重复的分钟。先从第 0 条开始。
- 5紫色指针落在第 0 条日志「0,5」,拆开看是用户 0 在第 5 分钟操作。到右边找用户 0 这一行,他现在的分钟集合是 { }。这是用户 0 第一次出现,给他新开一行空集合。
- 6分钟 5 是用户 0 的新分钟,加进集合后变成 { 5 },大小来到 1。这一条处理完,指针会挪到下一格。继续扫。
- 7紫色指针落在第 1 条日志「1,2」,拆开看是用户 1 在第 2 分钟操作。到右边找用户 1 这一行,他现在的分钟集合是 { }。这是用户 1 第一次出现,给他新开一行空集合。
- 8分钟 2 是用户 1 的新分钟,加进集合后变成 { 2 },大小来到 1。这一条处理完,指针会挪到下一格。继续扫。
- 9紫色指针落在第 2 条日志「0,2」,拆开看是用户 0 在第 2 分钟操作。到右边找用户 0 这一行,他现在的分钟集合是 { 5 }。这行被点亮,准备把分钟 2 加进去。
- 10分钟 2 是用户 0 的新分钟,加进集合后变成 { 5, 2 },大小来到 2。这一条处理完,指针会挪到下一格。继续扫。
- 11紫色指针落在第 3 条日志「2,4」,拆开看是用户 2 在第 4 分钟操作。到右边找用户 2 这一行,他现在的分钟集合是 { }。这是用户 2 第一次出现,给他新开一行空集合。
- 12分钟 4 是用户 2 的新分钟,加进集合后变成 { 4 },大小来到 1。这一条处理完,指针会挪到下一格。继续扫。
- 13紫色指针落在第 4 条日志「0,5」,拆开看是用户 0 在第 5 分钟操作。到右边找用户 0 这一行,他现在的分钟集合是 { 5, 2 }。这行被点亮,准备把分钟 5 加进去。
- 14注意这一条:分钟 5 早就在用户 0 的集合里了。Set 会把这次重复直接吞掉,集合还是 { 5, 2 },大小没变,仍是 2。这正是「同一分钟做几次也只算一次」的关键,活跃分钟数看的是不同分钟的个数。看下一条。
- 15紫色指针落在第 5 条日志「1,3」,拆开看是用户 1 在第 3 分钟操作。到右边找用户 1 这一行,他现在的分钟集合是 { 2 }。这行被点亮,准备把分钟 3 加进去。
- 16分钟 3 是用户 1 的新分钟,加进集合后变成 { 2, 3 },大小来到 2。这一条处理完,指针会挪到下一格。
- 176 条日志全部扫完,三个集合定型:用户 0 是 { 5, 2 },大小 2;用户 1 是 { 2, 3 },大小 2;用户 2 是 { 4 },大小 1。每个集合的大小,就是这个用户的活跃分钟数 UAM。注意用户 0 那条日志里 5 出现了两次,靠去重最后只留一个,UAM 才是 2 而不是 3。接下来进入第二步:按这三个大小去计票。
- 18现在换成答案数组登场,它长度是 k = 3,三格从左到右分别代表 UAM 等于 1、2、3 的用户数,一开始都是 0。右边这张表把三个用户的集合大小列出来当参照。接下来一个个用户看:他的集合多大,就给答案里对应那格加一票。要留意题目下标从 1 开始,而数组从 0 开始,所以 UAM 为 size 的用户,票落在第 size 减 1 这一格。
- 19轮到用户 0,他的集合大小是 2,也就是 UAM 等于 2。那就该往答案里「UAM 等于 2」的那格投一票,这格的数组下标是 2 减 1 等于 1,紫色指针停在这里,它现在的值是 0。
- 20给这格加一票:第 1 格从 0 变成 1,意思是 UAM 等于 2 的用户现在数到了 1 个。换下一个用户。
- 21轮到用户 1,他的集合大小是 2,也就是 UAM 等于 2。那就该往答案里「UAM 等于 2」的那格投一票,这格的数组下标是 2 减 1 等于 1,紫色指针停在这里,它现在的值是 1。
- 22给这格加一票:第 1 格从 1 变成 2,意思是 UAM 等于 2 的用户现在数到了 2 个。换下一个用户。
- 23轮到用户 2,他的集合大小是 1,也就是 UAM 等于 1。那就该往答案里「UAM 等于 1」的那格投一票,这格的数组下标是 1 减 1 等于 0,紫色指针停在这里,它现在的值是 0。
- 24给这格加一票:第 0 格从 0 变成 1,意思是 UAM 等于 1 的用户现在数到了 1 个。三个用户都投完了。
- 25三个用户都投完票,回看一遍:用户 2 的 UAM 是 1,让第 1 格得 1 票;用户 0 和用户 1 的 UAM 都是 2,让第 2 格得 2 票;没有人 UAM 是 3,第 3 格是 0。所以答案数组是 [1, 2, 0],和题面对得上。整道题就两步:先用「用户到分钟集合」的哈希表去重求出每人 UAM,再按集合大小往答案数组计票。用户投票的先后顺序不影响结果,换个顺序数,答案一样。
⚠️ 容易写错的地方
✗ 错：用列表或数组存每个用户的分钟,不去重,直接按长度当 UAM
✓ 对：一定要用 Set 集合去重:同一用户同一分钟只算一次
UAM 的定义是不同分钟的个数。本例用户 0 的日志里第 5 分钟出现两次,若不去重会把 UAM 算成 3,正确是 2。Set 的插入自带去重,是这题的核心,换成会记重复的容器就错了
✗ 错：计票时写成 ans[size] 加一,忘了减 1
✓ 对：必须 ans[size 减 1] 加一,把下标从 1 开始的 UAM 落到 0 基数组
题目答案下标从 1 开始,第 j 位记 UAM 为 j 的用户;而数组下标从 0 起。UAM 为 size 的用户应落在第 size 减 1 格。写成 ans[size] 会整体右移一格、还可能越界,是最常见的差一错误
✗ 错：担心用户遍历顺序不同会导致答案不同
✓ 对：计票只按集合大小累加,与用户先后无关,顺序随便
答案数组每一格是「某个 UAM 值的用户计数」,加法可交换,先数谁后数谁最终票数一样。哈希表遍历顺序本就不保证,但结果稳定,不用担心
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
unordered_map<int, unordered_set<int>> d;
for (auto& log : logs) {
int i = log[0], t = log[1];
d[i].insert(t);
}
vector<int> ans(k);
for (auto& [_, ts] : d) {
++ans[ts.size() - 1];
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int[] findingUsersActiveMinutes(int[][] logs, int k) {
Map<Integer, Set<Integer>> d = new HashMap<>();
for (int[] log : logs) {
int i = log[0], t = log[1];
d.computeIfAbsent(i, key -> new HashSet<>()).add(t);
}
int[] ans = new int[k];
for (Set<Integer> ts : d.values()) {
++ans[ts.size() - 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)。这里只额外存集合和计票数组,不存日志本身的副本
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 查找用户活跃分钟数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么每个用户要用集合 Set 而不是列表来存分钟?+
因为活跃分钟数看的是不同分钟的个数,同一分钟操作多次只算一次。Set 的插入自带去重,重复分钟塞进去会被自动吞掉,最后集合大小正好就是 UAM。若用列表存,会把重复分钟也记下来,长度比真实 UAM 大,还得再去重一遍,多此一举。用 Set 一步到位。
计票时那个减 1 是怎么来的,能省掉吗?+
题目要求答案数组下标从 1 开始,第 j 位记活跃分钟数为 j 的用户数。但大多数语言的数组下标从 0 开始,所以 UAM 为 size 的用户,要落在数组的第 size 减 1 格。这个减 1 是「从 1 计数」翻译到「从 0 计数」的桥梁,省不掉,除非你多开一格、下标 0 空着不用,那样代码可读性反而差。
三种语言在建集合上有什么细节差别?+
Python 用 defaultdict(set),访问不存在的键会自动建空集合,再 add 去重,最简洁。C++ 用 unordered_map 套 unordered_set,用中括号访问不存在的键也会默认构造一个空集合,再 insert。Java 用 HashMap 套 HashSet,得靠 computeIfAbsent 惰性建集合再 add,因为直接 get 不存在的键会返回空引用。三家去重逻辑一样,差别只在如何优雅地「键不存在就新建空集合」。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 查找用户活跃分钟数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。