原题: 1817.查找用户活跃分钟数

描述:

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

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

指定用户的 用户活跃分钟数（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^4
• 0 <= ID<sub>i</sub> <= 10^9
• 1 <= time<sub>i</sub> <= 10^5
• k 的取值范围是 [用户的最大用户活跃分钟数, 10- 5]

个人版答案

执行用时: 19 ms 执行内存消耗: 54.68 M

class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        int[] res = new int[k];
        Map<Integer/* id */, Set<Integer/* time */>> resMap = new HashMap<>();
        for(int i = 0; i < logs.length; i++){
            int id = logs[i][0];
            int time = logs[i][1];
            Set<Integer> s = resMap.getOrDefault(id, new HashSet<>());
            if(s.contains(time)){
                continue;
            }
            s.add(time);
            resMap.put(id, s);
        }
        for(Set<Integer> s: resMap.values()){
            if(s.size() > k){
                continue;
            }
            res[s.size()-1]++;
        }
        return res;
    }
}

优秀解法

执行耗时: 11 ms

class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        Arrays.sort(logs, (a, b) -> a[0] == b[0] ? a[1] - b[1]: a[0] - b[0]);
        int cnt = 0;
        int[] ans = new int[k];
        for (int i = 1; i < logs.length; ++i) {
            if (logs[i][0] == logs[i - 1][0]) {
                if (logs[i][1] == logs[i - 1][1]) continue;
                ++cnt;
                continue;
            }
            ++ans[cnt];
            cnt = 0;
        }
        ++ans[cnt];
        return ans;
    }
}

个人解题思路与优秀答案解析

题目分析及个人版思路

1. 语文题, 简单来说就是统计每个打点时间上有几个人, 然后把指定次数范围内的人筛出来.
2. 这样一来, 结合例题, 我们的思路就很明白嘞. 首先, 建立一个人的map. map的value放入一个时间集合. 因为题目说明, 在同一分钟不管多少次操作都算一次, 那么很容易的, 我们就想到了set. 当然用list先判断后放也行. 你看我就是这么做的. 虽然我使用了set.

    if(s.contains(time)){
        continue;
    }

这一步多次一举, 当然, 我在写的时候还是沾沾自喜的. 判断的如此精密...哈哈哈哈哈哈哈
3. 统计后再来一次map的循环. 拿value的set的size往结果数组中+1即可..哈哈哈哈

进阶版思路
这是正常人能想出来的? 这是专门刷题的竞赛选手吧?
解题思路一致, 但是...我还是不明白, 正常人真的会这么0帧起手么?

先对数组排序, 把人和分钟从小到大排列出来
然后遍历二维数组, 根据人来统计出现的分钟数...
太优雅了...我还是老老实实看大门吧