算法刷题打卡第71天查找用户活跃分钟数
查找用户活跃分钟数
难度:中等
给你用户在 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:
输入: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 ≤ j ≤ k 1 \le j \le k 1≤j≤k的每个 j j j 计算用户活跃分钟数等于 j j j 的用户数。需要首先得到每个用户的用户活跃分钟数,然后计算用户活跃分钟数等于特定值的用户数。
由于同一个用户的每次执行操作的时间不重复计算,因此需要使用哈希表记录每个用户的执行操作的时间,哈希表的关键字是用户编号,哈希表的值是存储执行操作的分钟的哈希集合,使用哈希集合可以确保同一个用户执行操作的同一分钟只会计算一次,不会重复计算。
首先遍历操作日志数组 logs \textit{logs} logs 得到每个用户对应的执行操作的时间并存入哈希表,然后遍历哈希表并更新答案数组。由于这道题只需要知道用户活跃分钟数等于特定值的用户数,不需要知道具体的用户编号,因此只需要遍历哈希表中每条记录的值即可。哈希表中的每条记录的值都是一个哈希集合,哈希集合的元素个数等于当前用户的用户活跃分钟数,将答案数组中的对应元素值加 1 1 1。遍历哈希表中每条记录的值之后,即可得到答案数组。
由于答案数组的下标从 1 1 1 开始,因此在更新答案数组时需要注意将下标做转换。
复杂度分析:
-
时间复杂度: O ( n k ) O(n k) O(n k),其中 n n n 是数组 logs \textit{logs} logs 的长度, k k k 是给定的整数。遍历数组 logs \textit{logs} logs 并使用哈希表记录每个用户的活跃分钟需要 O ( n ) O(n) O(n) 的时间,创建答案数组和遍历哈希表更新答案数组需要 O ( n k ) O(n k) O(n k) 的时间,因此时间复杂度是 O ( n k ) O(n k) O(n k)。
-
空间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 logs \textit{logs} logs 的长度。哈希表需要 O ( n ) O(n) O(n) 的空间。注意返回值不计入空间复杂度。
class Solution:
def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
user_time = dict()
for i in logs:
if user_time.get(i[0]):
user_time[i[0]].add(i[1])
else:
user_time[i[0]] = set([i[1]])
res = k * [0]
for i in user_time.values():
res[len(i) - 1] = 1
return res
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/finding-the-users-active-minutes
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfifjje
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01