Sponsored
Sponsored
This approach involves using hash maps (or dictionaries) to track the number of matches each player has won and lost. We loop over the matches to populate these maps. Finally, we iterate over the accumulated data to build the two result lists: players with zero losses and players with exactly one loss. We then sort these lists before returning them.
Time Complexity: O(n log n) due to the sorting of players.
Space Complexity: O(n) for storing player and loss information.
1import java.util.*;
2class Solution {
3 public List<List<Integer>> findWinners(int[][] matches) {
4 Map<Integer, Integer> countMap = new HashMap<>();
5 Set<Integer> allPlayers = new HashSet<>();
6 for (int[] match : matches) {
7 allPlayers.add(match[0]);
8 allPlayers.add(match[1]);
9 countMap.put(match[1], countMap.getOrDefault(match[1], 0) + 1);
10 }
11 List<Integer> noLosses = new ArrayList<>();
12 List<Integer> oneLoss = new ArrayList<>();
13 for (int player : allPlayers) {
14 int loss = countMap.getOrDefault(player, 0);
15 if (loss == 0) {
16 noLosses.add(player);
17 } else if (loss == 1) {
18 oneLoss.add(player);
19 }
20 }
21 Collections.sort(noLosses);
22 Collections.sort(oneLoss);
23 List<List<Integer>> answer = new ArrayList<>();
24 answer.add(noLosses);
25 answer.add(oneLoss);
26 return answer;
27 }
28}In Java, we utilized HashMaps to count losses and track all players, similar to the Python approach. We then retrieve and categorize players' loss counts, sort the two lists, and return them.
In this approach, we maintain two numerical arrays or lists: one to track whether a player has won, and another to count how many times a player has lost. We then deduce the needed lists by examining these arrays.
Time Complexity: O(n log n)
Space Complexity: O(n)
1#include <vector>
2#include <algorithm>
3using namespace std;
4vector<vector<int>> findWinners(vector<vector<int>>& matches) {
5 vector<int> losses(100001, 0), played(100001, 0);
for (auto& match : matches) {
played[match[0]] = 1;
played[match[1]] = 1;
losses[match[1]]++;
}
vector<int> noLosses, oneLoss;
for (int i = 1; i <= 100000; ++i) {
if (played[i]) {
if (losses[i] == 0) noLosses.push_back(i);
else if (losses[i] == 1) oneLoss.push_back(i);
}
}
return {noLosses, oneLoss};
}Using two arrays of size 100,001 ensures constant time access for any player index. The 'losses' array stores the count of losses for each player, and the 'played' array indicates whether a player has participated. Finally, we evaluate these arrays to find and sort players with zero or one loss.