Problem#
給你一個陣列 match[i] = (winner_i, loser_i)
代表winner_i
在第 i
場比賽贏了 loser_i
,要你回傳沒有輸過的人、和只輸一場的人有哪些(回傳要遞增排序)。
測資限制#
- $1 \le n \le 10^5$
- $1 \le \text{winner}_i, \text{loser}_i \le 10^5$
想法#
統計贏家與輸家各自的場數,可以用 map
/unordered_map
,去所有贏家中找看誰沒出現在輸家中過(沒有輸過),則加到贏家答案中;找輸家中只輸一場的人,加到輸家答案中。
AC Code#
- 時間複雜度: $\mathcal{O}(n\log{n})$
- 空間複雜度: $\mathcal{O}(n)$
心得#
應該是 Easy