Leetcode 2225. Find Players With Zero or One Losses

题目

解法1：无序hashmap+排序

maintain一个dict，记录所有loser及其lose掉的match数量。遍历所有player，如果没在loser dict出现则是答案的第一维·，如果loser dict中的value是1，则是答案的第二维，最后将答案排序

class Solution:def findWinners(self, matches: List[List[int]]) -> List[List[int]]:# win_dict = collections.defaultdict(int)lose_dict = collections.defaultdict(int)all_players = set()for match in matches:p1_win = match[0]p2_lose = match[1]lose_dict[p2_lose] += 1all_players.add(p1_win)all_players.add(p2_lose)res = [[],[]]for p in all_players:if p not in lose_dict:res[0].append(p)elif lose_dict[p] == 1:res[1].append(p)res[0].sort()res[1].sort()return res

时间复杂度：O(nlogn)
空间复杂度：O(n)

解法2：使用有序hashmap

这个python可能没有对应解法，好像只有c++存在的std::map中的key是有序的，但是由于map查找元素是logn的，所以总体复杂度应该是一样的

class Solution {
    
public:vector<vector<int>> findWinners(vector<vector<int>>& matches) {
    map<int,int> mp;for(auto& match : matches){
    if(!mp.count(match[0])) mp[match[0]] = 0;mp[match[1]]++;}vector<vector<int>> res(2);for(auto& el : mp){
    if(el.second == 0){
    res[0].push_back(el.first);}else if(el.second == 1){
    res[1].push_back(el.first);}}return res;}
};

时间复杂度：O(nlogn)
空间复杂度：O(n)