题目描述

给你用户在 LeetCode 的操作日志，和一个整数 k。日志用一个二维整数数组 logs 表示，其中每个 logs[i] = [ID_i, time_i] 表示 ID 为 ID_i 的用户在 time_i 分钟时执行了某个操作。

多个用户 可以同时执行操作，单个用户可以在同一分钟内执行 多个操作。

指定用户的 用户活跃分钟数（user active minutes，UAM） 定义为用户对 LeetCode 执行操作的 唯一分钟数。即使一分钟内执行多个操作，也只能按一分钟计数。

请你统计用户活跃分钟数的分布情况，统计结果是一个长度为 k 且 下标从 1 开始计数 的数组 answer，对于每个 j（1 <= j <= k），answer[j] 表示 用户活跃分钟数 等于 j 的用户数。

返回上面描述的答案数组 answer。

样例

输入：logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
输出：[0,2,0,0,0]
解释：
ID=0 的用户执行操作的分钟分别是：5 、2 和 5。因此，该用户的用户活跃分钟数为 2（分钟 5 只计数一次）。
ID=1 的用户执行操作的分钟分别是：2 和 3。因此，该用户的用户活跃分钟数为 2。
2 个用户的用户活跃分钟数都是 2，answer[2] 为 2，其余 answer[j] 的值都是 0。

输入：logs = [[1,1],[2,2],[2,3]], k = 4
输出：[1,1,0,0]
解释：
ID=1 的用户仅在分钟 1 执行单个操作。因此，该用户的用户活跃分钟数为 1。
ID=2 的用户执行操作的分钟分别是：2 和 3。因此，该用户的用户活跃分钟数为 2。
1 个用户的用户活跃分钟数是 1 ，1 个用户的用户活跃分钟数是 2。
因此，answer[1] = 1，answer[2] = 1，其余的值都是 0。

限制

• 1 <= logs.length <= 10^4
• 0 <= ID_i <= 10^9
• 1 <= time_i <= 10^5
• k 的取值范围是 [用户的最大用户活跃分钟数, 10^5]。

算法

(哈希表) $O(n)$

1. 将每条日志存储哈希表，哈希表的 key 为用户 ID，值为一个无重复的集合。
2. 最后遍历哈希表，累计每个用户的访问集合的 size。

时间复杂度

• 每条日志存储哈希表的时间为常数，最后遍历一次哈希表。
• 故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
        vector<int> ans(k, 0);
        unordered_map<int, unordered_set<int>> seen;

        for (const auto &v : logs)
            seen[v[0]].insert(v[1]);

        for (const auto &[_, v] : seen)
            ans[v.size() - 1]++;

        return ans;
    }
};