Problem#
給你一個陣列 match[i] = (winner_i, loser_i)
代表winner_i
在第 i
場比賽贏了 loser_i
,要你回傳沒有輸過的人、和只輸一場的人有哪些(回傳要遞增排序)。
測資限制#
- 1≤n≤105
- 1≤winneri,loseri≤105
想法#
統計贏家與輸家各自的場數,可以用 map
/unordered_map
,去所有贏家中找看誰沒出現在輸家中過(沒有輸過),則加到贏家答案中;找輸家中只輸一場的人,加到輸家答案中。
AC Code#
Copy
class Solution { public: vector<vector<int>> findWinners(vector<vector<int>>& matches) { vector<vector<int>> ans(2); int n = matches.size(); unordered_map<int, int> wm, lm; for(auto i : matches) { auto [w, l] = tie(i[0], i[1]); wm[w]++; lm[l]++; } for(auto [i, cnt] : wm) { if(!lm.count(i)) ans[0].push_back(i); } for(auto [i, cnt] : lm) { if(cnt == 1) ans[1].push_back(i); } for(int i = 0; i < 2; i++) sort(ans[i].begin(), ans[i].end()); return ans; } };
- 時間複雜度: O(nlogn)
- 空間複雜度: O(n)
心得#
應該是 Easy