Leetcode 2225. Find Players With Zero or One Losses

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] += 1
            all_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)

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

class Solution {
public:
    vector> findWinners(vector>& matches) {
        map mp;
        for(auto& match : matches){
            if(!mp.count(match[0])) mp[match[0]] = 0;
            mp[match[1]]++;
        }
        vector> 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)