You are given the logs for users’ actions on LeetCode, and an integer k
. The logs are represented by a 2D integer array logs
where each logs[i] = [IDi, timei]
indicates that the user with IDi
performed an action at the minute timei
.
Multiple users can perform actions simultaneously, and a single user can perform multiple actions in the same minute.
The user active minutes (UAM) for a given user is defined as the number of unique minutes in which the user performed an action on LeetCode. A minute can only be counted once, even if multiple actions occur during it.
You are to calculate a 1-indexed array answer
of size k
such that, for each j
(1 <= j <= k
), answer[j]
is the number of users whose UAM equals j
.
Return the array answer
as described above.
Example 1:
Input: logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5 Output: [0,2,0,0,0] Explanation: The user with ID=0 performed actions at minutes 5, 2, and 5 again. Hence, they have a UAM of 2 (minute 5 is only counted once). The user with ID=1 performed actions at minutes 2 and 3. Hence, they have a UAM of 2. Since both users have a UAM of 2, answer[2] is 2, and the remaining answer[j] values are 0.
Example 2:
Input: logs = [[1,1],[2,2],[2,3]], k = 4 Output: [1,1,0,0] Explanation: The user with ID=1 performed a single action at minute 1. Hence, they have a UAM of 1. The user with ID=2 performed actions at minutes 2 and 3. Hence, they have a UAM of 2. There is one user with a UAM of 1 and one with a UAM of 2. Hence, answer[1] = 1, answer[2] = 1, and the remaining values are 0.
Constraints:
1 <= logs.length <= 104
0 <= IDi <= 109
1 <= timei <= 105
k
is in the range[The maximum UAM for a user, 105]
.
Solution: Hashsets in a Hashtable
key: user_id, value: set{time}
Time complexity: O(n + k)
Space complexity: O(n + k)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) { unordered_map<int, unordered_set<int>> m; vector<int> ans(k); for (const auto& log : logs) m[log[0]].insert(log[1]); for (const auto& [id, s] : m) ++ans[s.size() - 1]; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment