查找用户活跃分钟数

难度: Medium

给你用户在 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 。

示例 1：

输入：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

示例 2：

输入：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⁴
0 <= ID_i <= 10⁹
1 <= time_i <= 10⁵
k 的取值范围是 [用户的最大用户活跃分钟数, 10⁵]

Submission

运行时间: 66 ms

内存: 22.3 MB

class Solution:
    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
        ld = collections.defaultdict(set)
        for i,t in logs:
            ld[i].add(t)

        sc = [len(v) for v in ld.values()]
        scc = Counter(sc)

        r = [0]*k
        for cc in scc:
            r[cc-1]=scc[cc]
        return r

Explain

首先使用哈希表来存储每个用户对应的操作时间集合，确保时间的唯一性。遍历日志数组，将每个用户ID的操作时间添加到对应的集合中。这样可以计算出每个用户的活跃分钟数（即集合的大小）。之后，使用另一个哈希表来统计各个活跃分钟数的用户数量。最终，根据这个统计结果生成一个长度为k的数组，数组的第j个位置表示活跃分钟数为j的用户数量。

时间复杂度: O(n)

空间复杂度: O(u + t + k)

class Solution:
    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
        # 使用哈希表存储每个用户的唯一操作时间
        user_to_minutes = collections.defaultdict(set)
        for user_id, time in logs:
            user_to_minutes[user_id].add(time)

        # 计算每个用户的活跃分钟数并统计频率
        minute_counts = [len(minutes) for minutes in user_to_minutes.values()]
        count_frequencies = Counter(minute_counts)

        # 初始化结果数组
        result = [0] * k
        # 填充结果数组，其中索引对应的是活跃分钟数-1
        for count, freq in count_frequencies.items():
            if count <= k:
                result[count - 1] = freq

        return result

Explore

在解法中，`Counter` 类用于统计每个用户的活跃分钟数（即集合的大小）的频率。具体来说，我们首先通过遍历哈希表 `user_to_minutes` 的值（每个用户的操作时间集合）来创建一个活跃分钟数的列表。`Counter` 接着用于对这个列表中的活跃分钟数进行计数，从而得到每个不同的活跃分钟数对应的用户数量。这种方法可以快速地统计频率，因为 `Counter` 的底层实现是哈希表，其平均时间复杂度为 O(1)。因此，对于统计活跃分钟数的频率这一步骤，`Counter` 提供了高效的性能。

在代码的实现中，如果某个用户的活跃分钟数超过 `k`，在填充结果数组 `result` 的时候，我们只考虑活跃分钟数小于等于 `k` 的情况。这是通过 `if count <= k` 的条件判断实现的。超过 `k` 的活跃分钟数不会被加入到 `result` 数组中，因为 `result` 的长度固定为 `k`，且数组的索引是从0到k-1，对应的是活跃分钟数从1到k。因此，超过 `k` 的活跃分钟数在这个统计中被忽略。

在日志非常密集的情况下（例如，单个用户有大量不重复的时间戳），每个用户的集合大小会增加，但这不会显著影响哈希表操作的平均时间复杂度，仍然保持在 O(1)。在日志非常稀疏的情况下（即很少重复的用户ID或时间戳），哈希表的大小会较小，操作效率依然很高。整体而言，算法的时间复杂度主要取决于日志的总条目数，即 O(N)，其中 N 是日志数组的长度。因此，无论是密集还是稀疏的日志，性能都保持在一个合理的水平。

在代码实现中，结果数组 `result` 通过 `result = [0] * k` 初始化，确保其长度为 `k`。这个数组的每个索引位置 `i` 表示活跃分钟数为 `i+1` 的用户数量。通过遍历 `count_frequencies`，我们将活跃分钟数 `count` 和对应的用户数量 `freq` 填入到 `result[count - 1]` 的位置，只要 `count` 的值不超过 `k`。这样处理确保了数组不会越界，并且能够正确反映从1到k的每个活跃分钟数的用户数量。