{"id":9620,"date":"2022-04-02T21:54:47","date_gmt":"2022-04-03T04:54:47","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9620"},"modified":"2022-04-02T22:57:07","modified_gmt":"2022-04-03T05:57:07","slug":"leetcode-2225-find-players-with-zero-or-one-losses","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-2225-find-players-with-zero-or-one-losses\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2225. Find Players With Zero or One Losses"},"content":{"rendered":"\n<p>You are given an integer array&nbsp;<code>matches<\/code>&nbsp;where&nbsp;<code>matches[i] = [winner<sub>i<\/sub>, loser<sub>i<\/sub>]<\/code>&nbsp;indicates that the player&nbsp;<code>winner<sub>i<\/sub><\/code>&nbsp;defeated player&nbsp;<code>loser<sub>i<\/sub><\/code>&nbsp;in a match.<\/p>\n\n\n\n<p>Return&nbsp;<em>a list&nbsp;<\/em><code>answer<\/code><em>&nbsp;of size&nbsp;<\/em><code>2<\/code><em>&nbsp;where:<\/em><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>answer[0]<\/code>&nbsp;is a list of all players that have&nbsp;<strong>not<\/strong>&nbsp;lost any matches.<\/li><li><code>answer[1]<\/code>&nbsp;is a list of all players that have lost exactly&nbsp;<strong>one<\/strong>&nbsp;match.<\/li><\/ul>\n\n\n\n<p>The values in the two lists should be returned in&nbsp;<strong>increasing<\/strong>&nbsp;order.<\/p>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>You should only consider the players that have played&nbsp;<strong>at least one<\/strong>&nbsp;match.<\/li><li>The testcases will be generated such that&nbsp;<strong>no<\/strong>&nbsp;two matches will have the&nbsp;<strong>same<\/strong>&nbsp;outcome.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]\n<strong>Output:<\/strong> [[1,2,10],[4,5,7,8]]\n<strong>Explanation:<\/strong>\nPlayers 1, 2, and 10 have not lost any matches.\nPlayers 4, 5, 7, and 8 each have lost one match.\nPlayers 3, 6, and 9 each have lost two matches.\nThus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> matches = [[2,3],[1,3],[5,4],[6,4]]\n<strong>Output:<\/strong> [[1,2,5,6],[]]\n<strong>Explanation:<\/strong>\nPlayers 1, 2, 5, and 6 have not lost any matches.\nPlayers 3 and 4 each have lost two matches.\nThus, answer[0] = [1,2,5,6] and answer[1] = [].\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= matches.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>matches[i].length == 2<\/code><\/li><li><code>1 &lt;= winner<sub>i<\/sub>, loser<sub>i<\/sub>&nbsp;&lt;= 10<sup>5<\/sup><\/code><\/li><li><code>winner<sub>i<\/sub>&nbsp;!= loser<sub>i<\/sub><\/code><\/li><li>All&nbsp;<code>matches[i]<\/code>&nbsp;are&nbsp;<strong>unique<\/strong>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable<\/strong><\/h2>\n\n\n\n<p>Use a hashtable to store the number of matches each player has lost. Note, also create an entry for those winners who never lose.<\/p>\n\n\n\n<p>Time complexity: O(m), m = # of matches<br>Space complexity: O(n), n = # of players<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<vector<int>> findWinners(vector<vector<int>>& matches) {\n    unordered_map<int, int> m;\n    for (const auto& match : matches) {\n      m[match[0]]; \/\/ create an entry for the winner.\n      ++m[match[1]];      \n    }\n    vector<vector<int>> ans(2);\n    for (const auto& [player, loses] : m)\n      if (loses <= 1) ans[loses].push_back(player);      \n    sort(begin(ans[0]), end(ans[0]));\n    sort(begin(ans[1]), end(ans[1]));\n    return ans;\n  }  \n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;matches&nbsp;where&nbsp;matches[i] = [winneri, loseri]&nbsp;indicates that the player&nbsp;winneri&nbsp;defeated player&nbsp;loseri&nbsp;in a match. Return&nbsp;a list&nbsp;answer&nbsp;of size&nbsp;2&nbsp;where: answer[0]&nbsp;is a list of all players that&#8230;<\/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":[82,177],"class_list":["post-9620","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9620","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=9620"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9620\/revisions"}],"predecessor-version":[{"id":9622,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9620\/revisions\/9622"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9620"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9620"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9620"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}