Loading [MathJax]/jax/output/HTML-CSS/jax.js

Leetcode 2225 - Find Players With Zero or One Losses

題目

Problem#

給你一個陣列 match[i] = (winner_i, loser_i) 代表winner_i 在第 i 場比賽贏了 loser_i,要你回傳沒有輸過的人、和只輸一場的人有哪些(回傳要遞增排序)。

測資限制#

  • 1n105
  • 1winneri,loseri105

想法#

統計贏家與輸家各自的場數,可以用 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;
}
};
view raw leetcode/2225.cpp delivered with ❤ by emgithub
  • 時間複雜度: O(nlogn)
  • 空間複雜度: O(n)

心得#

應該是 Easy