LeetCode 1817. 查找用户活跃分钟数 Map、Set题解，本题读懂题最重要。

题目

1817. 查找用户活跃分钟数

https://leetcode.cn/problems/finding-the-users-active-minutes/

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

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

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

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

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

思路

这个题不知道为啥读起来难懂！

题目核心求的是 用户活跃时长 -> 对应用户数。

其中针对某分钟内同一用户的操作，计数需去重。

我们可以使用

1

Map<Integer, Set<Integer>> userId2Minutes

来统计每个用户活跃的分钟数据，使用Set即可保证分钟数据去重。

之后再遍历一次，即可得出分钟数对应的用户数。

使用Map、Set

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

 /*
    * 执行用时：
    * 17 ms
    * , 在所有 Java 提交中击败了
    * 64.17%
    * 的用户
    * 内存消耗：
    * 51.8 MB
    * , 在所有 Java 提交中击败了
    * 15.84%
    * 的用户
    * 通过测试用例：
    * 38 / 38
    */
public int[] findingUsersActiveMinutes(int[][] logs, int k) {
    Map<Integer, Set<Integer>> userId2Minutes = new HashMap<>();
    for (int[] log : logs) {
        int userId = log[0];
        int minute = log[1];

        userId2Minutes.putIfAbsent(userId, new HashSet<>());
        Set<Integer> minutes = userId2Minutes.get(userId);
        minutes.add(minute);
    }
    int[] ans = new int[k];

    for (Map.Entry<Integer, Set<Integer>> entry : userId2Minutes.entrySet()) {
        Set<Integer> minutes = entry.getValue();
        ans[minutes.size() - 1] = ans[minutes.size() - 1] + 1;
    }

    return ans;
}

复杂度

m：logs行数 n：logs列数

时间

对数据遍历了行数，两次，复杂度O(m)。

空间

额外使用了userId2Minutes统计过程数据，叠加占用O(n*m)。