1817. 找到用户的活跃分钟数

Medium

题目描述

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

多个用户可以同时执行行为，单个用户也可以在同一分钟内执行多次行为。

某指定用户的 用户活跃分钟数（UAM） 定义为用户在 LeetCode 上执行行为的 不同分钟数。即使一分钟内执行多个行为，该分钟也只能按一次计算。

你需要计算一个长度为 k、下标从 1 开始 的数组 answer，对于每个 j（1 <= j <= k），answer[j] 是 UAM 等于 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 分钟执行了行为。因此，该用户的 UAM 为 2（第 5 分钟只计算一次）。
ID=1 的用户在第 2、3 分钟执行了行为。因此，该用户的 UAM 为 2。
由于两个用户的 UAM 都是 2，所以 answer[2] 是 2，其余 answer[j] 的值都是 0。

示例 2：

输入：logs = [[1,1],[2,2],[2,3]], k = 4
输出：[1,1,0,0]
解释：
ID=1 的用户在第 1 分钟执行了一次行为。因此，该用户的 UAM 为 1。
ID=2 的用户在第 2、3 分钟执行了行为。因此，该用户的 UAM 为 2。
有一个用户的 UAM 是 1，一个用户的 UAM 是 2。
因此，answer[1] = 1, answer[2] = 1，其余的值都是 0。

约束条件：

1 <= logs.length <= 10^4
0 <= IDi <= 10^9
1 <= timei <= 10^5
k 的范围在 [某用户的最大 UAM, 10^5] 内。

解题思路

这道题需要统计每个用户的活跃分钟数（UAM），然后计算有多少用户的UAM等于每个可能的值。

核心思路：

统计每个用户的不同分钟数：使用哈希表存储每个用户ID对应的不重复时间分钟集合
计算UAM分布：遍历所有用户，统计每个UAM值对应的用户数量

具体步骤：

使用 map<int, set<int>> 结构，键为用户ID，值为该用户活跃的分钟集合
遍历日志数组，将每个用户的活跃分钟加入对应集合（set自动去重）
创建长度为k的结果数组，初始化为0
遍历所有用户，统计每个用户的UAM（即set的大小），在结果数组对应位置+1

时间复杂度分析：

构建用户活跃分钟映射：O(n log m)，其中n是日志数，m是平均每用户的不同分钟数
统计UAM分布：O(u)，其中u是用户数
总体：O(n log m + u)

这种方法简洁高效，充分利用了set的去重特性和map的快速查找能力。

代码实现

class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
        unordered_map<int, unordered_set<int>> userMinutes;
        
        // 统计每个用户的不同活跃分钟
        for (auto& log : logs) {
            userMinutes[log[0]].insert(log[1]);
        }
        
        vector<int> result(k, 0);
        
        // 统计每个UAM值对应的用户数量
        for (auto& [user, minutes] : userMinutes) {
            int uam = minutes.size();
            if (uam >= 1 && uam <= k) {
                result[uam - 1]++;
            }
        }
        
        return result;
    }
};

class Solution:
    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
        user_minutes = {}
        
        # 统计每个用户的不同活跃分钟
        for user_id, time in logs:
            if user_id not in user_minutes:
                user_minutes[user_id] = set()
            user_minutes[user_id].add(time)
        
        result = [0] * k
        
        # 统计每个UAM值对应的用户数量
        for minutes_set in user_minutes.values():
            uam = len(minutes_set)
            if 1 <= uam <= k:
                result[uam - 1] += 1
        
        return result

public class Solution {
    public int[] FindingUsersActiveMinutes(int[][] logs, int k) {
        var userMinutes = new Dictionary<int, HashSet<int>>();
        
        // 统计每个用户的不同活跃分钟
        foreach (var log in logs) {
            int userId = log[0];
            int time = log[1];
            
            if (!userMinutes.ContainsKey(userId)) {
                userMinutes[userId] = new HashSet<int>();
            }
            userMinutes[userId].Add(time);
        }
        
        int[] result = new int[k];
        
        // 统计每个UAM值对应的用户数量
        foreach (var minutesSet in userMinutes.Values) {
            int uam = minutesSet.Count;
            if (uam >= 1 && uam <= k) {
                result[uam - 1]++;
            }
        }
        
        return result;
    }
}

var findingUsersActiveMinutes = function(logs, k) {
    const userMinutes = new Map();
    
    // 统计每个用户的不同活跃分钟
    for (const [userId, time] of logs) {
        if (!userMinutes.has(userId)) {
            userMinutes.set(userId, new Set());
        }
        userMinutes.get(userId).add(time);
    }
    
    const result = new Array(k).fill(0);
    
    // 统计每个UAM值对应的用户数量
    for (const minutesSet of userMinutes.values()) {
        const uam = minutesSet.size;
        if (uam >= 1 && uam <= k) {
            result[uam - 1]++;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(n log m)，其中 n 是日志数量，m 是平均每用户的不同分钟数
空间复杂度	O(u × m)，其中 u 是用户数量，m 是平均每用户的不同分钟数

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析