{"id":8323,"date":"2021-04-06T17:05:02","date_gmt":"2021-04-07T00:05:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8323"},"modified":"2021-04-06T23:08:05","modified_gmt":"2021-04-07T06:08:05","slug":"leetcode-1817-finding-the-users-active-minutes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1817-finding-the-users-active-minutes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1817. Finding the Users Active Minutes"},"content":{"rendered":"\n

You are given the logs for users’ actions on LeetCode, and an integer k<\/code>. The logs are represented by a 2D integer array logs<\/code> where each logs[i] = [IDi<\/sub>, timei<\/sub>]<\/code> indicates that the user with IDi<\/sub><\/code> performed an action at the minute timei<\/sub><\/code>.<\/p>\n\n\n\n

Multiple users<\/strong> can perform actions simultaneously, and a single user can perform multiple actions<\/strong> in the same minute.<\/p>\n\n\n\n

The user active minutes (UAM)<\/strong> for a given user is defined as the number of unique minutes<\/strong> in which the user performed an action on LeetCode. A minute can only be counted once, even if multiple actions occur during it.<\/p>\n\n\n\n

You are to calculate a 1-indexed<\/strong> array answer<\/code> of size k<\/code> such that, for each j<\/code> (1 <= j <= k<\/code>), answer[j]<\/code> is the number of users<\/strong> whose UAM<\/strong> equals j<\/code>.<\/p>\n\n\n\n

Return the array <\/em>answer<\/code> as described above<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5\nOutput:<\/strong> [0,2,0,0,0]\nExplanation:<\/strong>\nThe 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).\nThe user with ID=1 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.\nSince both users have a UAM of 2, answer[2] is 2, and the remaining answer[j] values are 0.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> logs = [[1,1],[2,2],[2,3]], k = 4\nOutput:<\/strong> [1,1,0,0]\nExplanation:<\/strong>\nThe user with ID=1 performed a single action at minute 1. Hence, they have a UAM of 1.\nThe user with ID=2 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.\nThere is one user with a UAM of 1 and one with a UAM of 2.\nHence, answer[1] = 1, answer[2] = 1, and the remaining values are 0.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= logs.length <= 104<\/sup><\/code><\/li>
  • 0 <= IDi<\/sub> <= 109<\/sup><\/code><\/li>
  • 1 <= timei<\/sub> <= 105<\/sup><\/code><\/li>
  • k<\/code> is in the range [The maximum UAM<\/strong> for a user, 105<\/sup>]<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Hashsets in a Hashtable<\/strong><\/h2>\n\n\n\n
    key: user_id, value: set{time} <\/p>\n\n\n\n
    Time complexity: O(n + k)
    Space complexity: O(n + k)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  vector findingUsersActiveMinutes(vector>& logs, int k) {\n    unordered_map> m;\n    vector ans(k);\n    for (const auto& log : logs)\n      m[log[0]].insert(log[1]);\n    for (const auto& [id, s] : m)\n      ++ans[s.size() - 1];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n

    <\/p>\n","protected":false},"excerpt":{"rendered":"
    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,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[8,299,82,177],"class_list":["post-8323","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-counting","tag-hashset","tag-hashtable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8323","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8323"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8323\/revisions"}],"predecessor-version":[{"id":8333,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8323\/revisions\/8333"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8323"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8323"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8323"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}