LeetCode 2225: Find Players With Zero or One Losses (Single Pass + Loss Counter)
LeetCode 2225Hash TableCountingToday we solve LeetCode 2225 - Find Players With Zero or One Losses.
Source: https://leetcode.com/problems/find-players-with-zero-or-one-losses/
English
Problem Summary
Given match results [winner, loser], return two sorted lists: players who never lost, and players who lost exactly once.
Key Insight
Each match only affects two facts: both players should appear in our record, and the loser's loss count increases by one. So a single pass with a loss counter map is enough.
Algorithm
- Maintain losses[player].
- For each match, initialize winner with 0 losses if absent.
- Increment loser's losses by 1.
- Scan the map: count 0 into list A, count 1 into list B.
- Sort both lists and return [A, B].
Complexity Analysis
Let m be number of matches and k be number of distinct players.
Time: O(m + k log k) (sorting dominates).
Space: O(k).
Common Pitfalls
- Forgetting to insert winners who never appear as losers.
- Returning unsorted lists.
- Accidentally including players with loss count > 1 in the second list.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<List<Integer>> findWinners(int[][] matches) {
Map<Integer, Integer> losses = new HashMap<>();
for (int[] match : matches) {
int winner = match[0], loser = match[1];
losses.putIfAbsent(winner, 0);
losses.put(loser, losses.getOrDefault(loser, 0) + 1);
}
List<Integer> zero = new ArrayList<>();
List<Integer> one = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : losses.entrySet()) {
if (e.getValue() == 0) zero.add(e.getKey());
else if (e.getValue() == 1) one.add(e.getKey());
}
Collections.sort(zero);
Collections.sort(one);
return Arrays.asList(zero, one);
}
}func findWinners(matches [][]int) [][]int {
losses := map[int]int{}
for _, match := range matches {
winner, loser := match[0], match[1]
if _, ok := losses[winner]; !ok {
losses[winner] = 0
}
losses[loser] = losses[loser] + 1
}
zero := []int{}
one := []int{}
for player, cnt := range losses {
if cnt == 0 {
zero = append(zero, player)
} else if cnt == 1 {
one = append(one, player)
}
}
sort.Ints(zero)
sort.Ints(one)
return [][]int{zero, one}
}class Solution {
public:
vector<vector<int>> findWinners(vector<vector<int>>& matches) {
unordered_map<int, int> losses;
for (auto &match : matches) {
int winner = match[0], loser = match[1];
if (!losses.count(winner)) losses[winner] = 0;
losses[loser]++;
}
vector<int> zero, one;
for (auto &kv : losses) {
if (kv.second == 0) zero.push_back(kv.first);
else if (kv.second == 1) one.push_back(kv.first);
}
sort(zero.begin(), zero.end());
sort(one.begin(), one.end());
return {zero, one};
}
};class Solution:
def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
losses = {}
for winner, loser in matches:
losses.setdefault(winner, 0)
losses[loser] = losses.get(loser, 0) + 1
zero = []
one = []
for player, cnt in losses.items():
if cnt == 0:
zero.append(player)
elif cnt == 1:
one.append(player)
zero.sort()
one.sort()
return [zero, one]var findWinners = function(matches) {
const losses = new Map();
for (const [winner, loser] of matches) {
if (!losses.has(winner)) losses.set(winner, 0);
losses.set(loser, (losses.get(loser) || 0) + 1);
}
const zero = [];
const one = [];
for (const [player, cnt] of losses.entries()) {
if (cnt === 0) zero.push(player);
else if (cnt === 1) one.push(player);
}
zero.sort((a, b) => a - b);
one.sort((a, b) => a - b);
return [zero, one];
};中文
题目概述
给定比赛结果 [winner, loser]，返回两个升序数组：从未输过的选手，以及恰好输过一次的选手。
核心思路
每场比赛只改变两件事：两名选手都要进入记录，输家的失败次数加一。因此用一个 losses 哈希表单次遍历即可完成统计。
算法步骤
- 用 losses[player] 记录失败次数。
- 遍历比赛时，先确保 winner 至少以 0 初始化。
- loser 的失败次数加 1。
- 遍历哈希表：次数为 0 放入第一组，次数为 1 放入第二组。
- 两组分别排序后返回。
复杂度分析
设比赛数为 m，不同选手数为 k。
时间复杂度：O(m + k log k)。
空间复杂度：O(k)。
常见陷阱
- 忘记把“只当过 winner”的选手加入结果候选。
- 输出前忘记排序。
- 把失败次数大于 1 的选手误放进第二组。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<List<Integer>> findWinners(int[][] matches) {
Map<Integer, Integer> losses = new HashMap<>();
for (int[] match : matches) {
int winner = match[0], loser = match[1];
losses.putIfAbsent(winner, 0);
losses.put(loser, losses.getOrDefault(loser, 0) + 1);
}
List<Integer> zero = new ArrayList<>();
List<Integer> one = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : losses.entrySet()) {
if (e.getValue() == 0) zero.add(e.getKey());
else if (e.getValue() == 1) one.add(e.getKey());
}
Collections.sort(zero);
Collections.sort(one);
return Arrays.asList(zero, one);
}
}func findWinners(matches [][]int) [][]int {
losses := map[int]int{}
for _, match := range matches {
winner, loser := match[0], match[1]
if _, ok := losses[winner]; !ok {
losses[winner] = 0
}
losses[loser] = losses[loser] + 1
}
zero := []int{}
one := []int{}
for player, cnt := range losses {
if cnt == 0 {
zero = append(zero, player)
} else if cnt == 1 {
one = append(one, player)
}
}
sort.Ints(zero)
sort.Ints(one)
return [][]int{zero, one}
}class Solution {
public:
vector<vector<int>> findWinners(vector<vector<int>>& matches) {
unordered_map<int, int> losses;
for (auto &match : matches) {
int winner = match[0], loser = match[1];
if (!losses.count(winner)) losses[winner] = 0;
losses[loser]++;
}
vector<int> zero, one;
for (auto &kv : losses) {
if (kv.second == 0) zero.push_back(kv.first);
else if (kv.second == 1) one.push_back(kv.first);
}
sort(zero.begin(), zero.end());
sort(one.begin(), one.end());
return {zero, one};
}
};class Solution:
def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
losses = {}
for winner, loser in matches:
losses.setdefault(winner, 0)
losses[loser] = losses.get(loser, 0) + 1
zero = []
one = []
for player, cnt in losses.items():
if cnt == 0:
zero.append(player)
elif cnt == 1:
one.append(player)
zero.sort()
one.sort()
return [zero, one]var findWinners = function(matches) {
const losses = new Map();
for (const [winner, loser] of matches) {
if (!losses.has(winner)) losses.set(winner, 0);
losses.set(loser, (losses.get(loser) || 0) + 1);
}
const zero = [];
const one = [];
for (const [player, cnt] of losses.entries()) {
if (cnt === 0) zero.push(player);
else if (cnt === 1) one.push(player);
}
zero.sort((a, b) => a - b);
one.sort((a, b) => a - b);
return [zero, one];
};
Comments