How do I approach the 'Finding the Users Active Minutes' problem?

Focus on scanning the logs array while using hash tables to group actions by user. Then, calculate the unique minutes each user was active and count the frequency of these active minute counts.

What data structures are useful for this problem?

Hash tables are crucial for grouping user actions, and sets are helpful for counting unique minutes of activity for each user.

How can I optimize my solution for large input sizes?

Ensure that you process each log entry once, and use efficient data structures like hash tables and sets to minimize unnecessary computation.

What is the time complexity of this solution?

The time complexity is O(n), where n is the number of logs, since each log entry is processed once.

What if multiple users perform actions at the same minute?

You count each minute only once per user. The key challenge is to store the unique minutes per user, which can be done using a set for each user.

#1817

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

查找用户活跃分钟数

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

数组哈希表

题目描述

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

lightbulb

解题思路

方法一：哈希表

我们用哈希表 $d$ 记录每个用户的所有去重操作时间，然后遍历哈希表，统计每个用户的用户活跃分钟数，最后统计每个用户活跃分钟数的分布情况。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $logs$ 的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's ability to efficiently use hash tables for grouping and counting.
question_mark
Check if the candidate can reason about the use of sets for counting unique minutes.
question_mark
Evaluate the candidate's understanding of time and space complexity trade-offs in this problem.

warning

常见陷阱

外企场景

error
Not using a set to count unique minutes, which could lead to over-counting for users with multiple actions at the same minute.
error
Failing to account for users with zero active minutes (resulting in incorrect array indexing).
error
Using inefficient data structures or algorithms that lead to unnecessary time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider edge cases where all actions occur at the same minute or all users have the same active minute count.
arrow_right_alt
What if the input logs contain many repeated user actions? How would your solution scale?
arrow_right_alt
What if k is smaller than the maximum unique minutes for any user? Can your solution still work within these constraints?

help

常见问题

外企场景

继续练习

#1814 统计一个数组中好对子的数目 #1807 替换字符串中的括号内容 #1782 统计点对的数目