查找用户活跃分钟数 图解题解

一堆操作日志，最后要数出什么

给一份操作日志 logs 和整数 k，每条日志是 [用户 ID, 分钟]，表示这个用户在这一分钟操作过。一个用户的活跃分钟数 UAM，就是他去重之后的不同分钟个数——同一分钟操作多次也只算一分钟。要返回长度 k、下标从 1 起的数组，第 j 位填「UAM 恰好等于 j 的用户数」。题面给的是 logs=[[0,5],[1,2],[0,2],[2,4],[0,5],[1,3]] 和 k 为 3，答案是 [1,2,0]。

拿日志两两互比着去重，为什么会拖成 O(n²)

求 UAM 得先弄清每个用户碰过哪些分钟、再去重。绕远的办法是每条日志和它前面所有日志两两对，看用户和分钟是否都撞上，日志 n 条就是 O(n²)，条数一多慢得没法看。

让容器自动把重复分钟吞掉，再开一块计票板

省事的做法是把去重交给容器。给每个用户挂一个集合，也就是塞进重复元素会被自动丢掉的容器，扫日志时把分钟往对应集合里塞，同一分钟塞第二次集合不变大，扫完集合大小正好就是这个用户的 UAM。

求出所有 UAM 后，不是逐个报数，而是桶计数：开一个长度 k 的答案数组当计票板，某用户 UAM 是 size 就往第 size 减 1 格投一票，投完每格票数就是「UAM 等于该值的用户数」。集合去重加桶计数，扫一趟日志、一趟用户就够。

两趟扫下来，减 1 那步是干什么用的

第一趟遍历每条日志 [i, t]，用哈希表按用户 i 找到他名下的集合，把分钟 t 加进去；用户第一次出现就先开个空集合。第二趟遍历每个集合，取出大小 size，执行 ans[size 减 1] 加一。这个减 1 是座桥：UAM 下标从 1 起、数组从 0 起，UAM 为 size 的用户得落在第 size 减 1 格。

六条日志，两趟后答案数组填成什么

第一趟建集合。读到 [0,5]，用户 0 的集合成 {5}；[1,2]，用户 1 成 {2}；[0,2]，用户 0 成 {5,2}；[2,4]，用户 2 成 {4}；[0,5]，分钟 5 早在用户 0 的集合里，被吞掉，集合还是 {5,2}；[1,3]，用户 1 成 {2,3}。三个集合定型，大小分别是 2、2、1。

第二趟计票。用户 0 的 size 是 2，ans[1] 从 0 加到 1；用户 1 也是 2，ans[1] 再加到 2；用户 2 的 size 是 1，ans[0] 从 0 加到 1；没人是 3，ans[2] 一直是 0。最终答案 [1,2,0]。

计票落在 ans[size] 而非 size 减 1，整排票右移

第一趟扫 n 条日志各做一次集合插入是常数，第二趟计票遍历元素不超过 n，再加长度 k 的数组，时间 O(n + k)、空间也是 O(n + k)，比两两互比的 O(n²) 快得多。最容易崴脚的是计票：把 ans[size 减 1] 写成 ans[size]，整排票集体右移一格，还可能在 size 等于 k 时越界。另一处坑是用列表存分钟不去重、直接拿长度当 UAM，用户 0 的分钟 5 出现两次就被算成 3、真实是 2。用户遍历顺序怎么变都不影响结果，计票只认集合大小。

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 ans

C++

#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;
    }
}