leetcode
leetcode 1601 ~ 1650
查找用户活跃分钟数

查找用户活跃分钟数

难度:

标签:

题目描述

代码结果

运行时间: 66 ms, 内存: 22.3 MB


/*
题目思路:
1. 使用 Java Stream API 处理 logs 数据,计算每个用户的活跃分钟数。
2. 使用 Map 来记录每个用户的活跃分钟数。
3. 使用 Map 合并用户活跃分钟数,统计每个活跃分钟数的用户数量。
4. 最后返回结果数组。
*/
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        Map<Integer, Set<Integer>> userMinutes = Arrays.stream(logs)
            .collect(Collectors.groupingBy(log -> log[0], Collectors.mapping(log -> log[1], Collectors.toSet())));
        return userMinutes.values().stream()
            .collect(Collectors.groupingBy(Set::size, Collectors.counting()))
            .entrySet().stream()
            .collect(Collectors.reducing(new int[k], (res, e) -> {
                if (e.getKey() <= k) res[e.getKey() - 1] = e.getValue().intValue();
                return res;
            }, (res1, res2) -> res1));
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(u + t + k)

代码细节讲解

🦆
类 `Counter` 在你的解法中具体是如何应用的,它对效率有什么影响?
在解法中,`Counter` 类用于统计每个用户的活跃分钟数(即集合的大小)的频率。具体来说,我们首先通过遍历哈希表 `user_to_minutes` 的值(每个用户的操作时间集合)来创建一个活跃分钟数的列表。`Counter` 接着用于对这个列表中的活跃分钟数进行计数,从而得到每个不同的活跃分钟数对应的用户数量。这种方法可以快速地统计频率,因为 `Counter` 的底层实现是哈希表,其平均时间复杂度为 O(1)。因此,对于统计活跃分钟数的频率这一步骤,`Counter` 提供了高效的性能。
🦆
在统计每个用户的活跃分钟数时,你是怎样处理用户活跃分钟数超过 `k` 的情况的?
在代码的实现中,如果某个用户的活跃分钟数超过 `k`,在填充结果数组 `result` 的时候,我们只考虑活跃分钟数小于等于 `k` 的情况。这是通过 `if count <= k` 的条件判断实现的。超过 `k` 的活跃分钟数不会被加入到 `result` 数组中,因为 `result` 的长度固定为 `k`,且数组的索引是从0到k-1,对应的是活跃分钟数从1到k。因此,超过 `k` 的活跃分钟数在这个统计中被忽略。
🦆
你的算法在面对极端情况,比如日志非常密集或非常稀疏时,性能表现如何?
在日志非常密集的情况下(例如,单个用户有大量不重复的时间戳),每个用户的集合大小会增加,但这不会显著影响哈希表操作的平均时间复杂度,仍然保持在 O(1)。在日志非常稀疏的情况下(即很少重复的用户ID或时间戳),哈希表的大小会较小,操作效率依然很高。整体而言,算法的时间复杂度主要取决于日志的总条目数,即 O(N),其中 N 是日志数组的长度。因此,无论是密集还是稀疏的日志,性能都保持在一个合理的水平。
🦆
你是如何保证最终结果数组 `result` 的长度恰好为 `k`,并正确处理所有可能的活跃分钟数的?
在代码实现中,结果数组 `result` 通过 `result = [0] * k` 初始化,确保其长度为 `k`。这个数组的每个索引位置 `i` 表示活跃分钟数为 `i+1` 的用户数量。通过遍历 `count_frequencies`,我们将活跃分钟数 `count` 和对应的用户数量 `freq` 填入到 `result[count - 1]` 的位置,只要 `count` 的值不超过 `k`。这样处理确保了数组不会越界,并且能够正确反映从1到k的每个活跃分钟数的用户数量。

相关问题