目标
给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。
返回一个长度为 2 的列表 answer ：
- answer[0] 是所有 没有 输掉任何比赛的玩家列表。
- answer[1] 是所有恰好输掉 一场 比赛的玩家列表。
两个列表中的值都应该按 递增 顺序返回。
注意：
- 只考虑那些参与 至少一场 比赛的玩家。
- 生成的测试用例保证 不存在 两场比赛结果 相同 。
示例 1：
输入：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
输出：[[1,2,10],[4,5,7,8]]
解释：
玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。
示例 2：
输入：matches = [[2,3],[1,3],[5,4],[6,4]]
输出：[[1,2,5,6],[]]
解释：
玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。
说明：
- 1 <= matches.length <= 10^5
- matches[i].length == 2
- 1 <= winneri, loseri <= 10^5
- winneri != loseri
- 所有 matches[i] 互不相同
思路
给定一个记录比赛结果的二维数组，数组元素为[winneri, loseri]，求没有输掉任何比赛的玩家以及仅输掉一场比赛的玩家。
简单实现可以直接利用TreeSet保存返回结果，往里面放的时候先判断是否输掉过比赛，如果后面输掉了比赛还要将其从从没输掉比赛的集合中移除。
对于仅输掉一次比赛的集合，不能根据它来判断是否输掉过比赛，因为输掉两次会从集合中移除，如何后续还会输掉比赛，判断集合中没有，就会错误地向其中添加，因此需要额外记录输掉过比赛的集合。
官网题解使用的是哈希表记录失败的次数，效率更高。
代码
/**
* @date 2024-05-22 9:03
*/
public class FindWinners2225 {
public List<List<Integer>> findWinners(int[][] matches) {
List<List<Integer>> res = new ArrayList<>();
Set<Integer> neverLose = new TreeSet<>();
Set<Integer> loseOnce = new TreeSet<>();
Set<Integer> lost = new HashSet<>();
for (int[] match : matches) {
int win = match[0];
int lose = match[1];
neverLose.remove(lose);
if (!lost.contains(win)) {
neverLose.add(win);
}
if (!loseOnce.contains(lose) && !lost.contains(lose)) {
loseOnce.add(lose);
} else {
loseOnce.remove(lose);
}
lost.add(lose);
}
List<Integer> winner = new ArrayList<>(neverLose);
List<Integer> loser = new ArrayList<>(loseOnce);
res.add(winner);
res.add(loser);
return res;
}
public List<List<Integer>> findWinners_v1(int[][] matches) {
Map<Integer, Integer> loseCnt = new HashMap<>(matches.length);
for (int[] match : matches) {
//可以直接在这里记录没有一次失败的
loseCnt.merge(match[1], 1, Integer::sum);
}
List<List<Integer>> res = new ArrayList<>();
Set<Integer> neverLose = new HashSet<>();
for (int[] match : matches) {
if(!loseCnt.containsKey(match[0])){
neverLose.add(match[0]);
}
}
List<Integer> winner = new ArrayList<>(neverLose);
Collections.sort(winner);
List<Integer> lostOnce = loseCnt.entrySet().stream()
.filter((entry) -> entry.getValue() == 1)
.map(Map.Entry::getKey).sorted()
.collect(Collectors.toList());
res.add(winner);
res.add(lostOnce);
return res;
}
}
性能
暴力解
哈希加排序
