Re: [閒聊] 每日LeetCode

2225. Find Players With Zero or One Losses 給你一個陣列matches，每個陣列裡面有兩個數字，第一個數字表示贏家編號，第二 個數字找出輸家編號，回傳一個List分別包含了沒輸過的玩家編號和只輸過一場的玩 家編號，玩家編號需要升序排列。 Example: Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]] Output: [[1,2,10],[4,5,7,8]] Explanation: Players 1, 2, and 10 have not lost any matches. Players 4, 5, 7, and 8 each have lost one match. Players 3, 6, and 9 each have lost two matches. Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8]. Constraints: 1 <= matches.length <= 10^5 matches[i].length == 2 1 <= winneri, loseri <= 10^5 winner[i] != loser[i] All matches[i] are unique. 方法一 TreeMap 思路： 1.首先，因為題目要找只輸過一場和沒輸過的玩家，所以我們要把所有（贏和輸） 的數字都加入到一個集合裡面，並去除輸超過一場的玩家，贏的次數不用統計只 要統計輸的即可。 2.再來，因為題目要求要排序所以我們統計每個玩家輸的次數，插入一個有序Map之中 3.遍歷Map從ID小的玩家編號開始插入answer，沒輸過為0的放第一個，只輸一場為1的 放第二個，其他不滿足條件的不插入。 JavaCode： ------------------------------------------------- class Solution { public List<List<Integer>> findWinners(int[][] matches) { Map<Integer,Integer> map = new TreeMap<>(); for (int[] match : matches) { int winner = match[0]; int loser = match[1]; if (!map.containsKey(winner)) map.put(winner, 0); map.put(loser, (map.get(loser) == null) ? 1 : map.get(loser) + 1); } List<List<Integer>> res = new ArrayList<>(); res.add(new ArrayList<>()); res.add(new ArrayList<>()); for (Map.Entry<Integer,Integer> entry : map.entrySet()) { if (entry.getValue() == null) { continue; } if (entry.getValue() == 0) { res.get(0).add(entry.getKey()); } else if (entry.getValue() == 1) { res.get(1).add(entry.getKey()); } } return res; } } ------------------------------------------------- 法二 計數排序 思路： 1.概念跟法一相同，但是因為測資範圍全部都是正數所以可以用計數排序來改善時間 複雜度 O(nlogn) => O(n + 10^5) Java Code： -------------------------------------------------- class Solution { public List<List<Integer>> findWinners(int[][] matches) { Integer[] players = new Integer[100001]; for (int[] match : matches) { int winner = match[0]; int loser = match[1]; if (players[winner] == null) { players[winner] = 0; } players[loser] = (players[loser] == null) ? 1 : players[loser] + 1; } List<List<Integer>> res = new ArrayList<>(); res.add(new ArrayList<>()); res.add(new ArrayList<>()); for (int i = 1; i < players.length; i++) { if (players[i] == null) { continue; } else if (players[i] == 0) { res.get(0).add(i); } else if (players[i] == 1) { res.get(1).add(i); } } return res; } } -------------------------------------------------- https://i.imgur.com/acHi4CL.png -- https://i.imgur.com/uiFto42.jpg --
※ 批踢踢實業坊(ptt.cc), 來自: 36.231.9.105 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1669603454.A.A94.html

推 sustainer123: 大師 11/28 10:48

推 PyTorch: 大師 11/28 10:51