2225.Find Players With Zero or One Losses
===

###### tags: `Medium`,`Array`,`Hash Table`,`Sorting`,`Counting`

[2225. Find Players With Zero or One Losses](https://leetcode.com/problems/find-players-with-zero-or-one-losses/)

### 題目描述

You are given an integer array `matches` where `matches[i] = [winner i, loser i]` indicates that the player $winner_i$ defeated player $loser_i$ in a match.

Return a *list* `answer` *of size* `2` *where:*

* `answer[0]` is a list of all players that have **not** lost any matches.
* `answer[1]` is a list of all players that have lost exactly **one** match.

The values in the two lists should be returned in **increasing** order.

**Note:**

* You should only consider the players that have played **at least one** match.
* The testcases will be generated such that **no** two matches will have the **same** outcome.

### 範例

**Example 1:**

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

**Example 2:**

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].

**Constraints**:

* 1 <= `matches.length` <= $10^5$
* `matches[i].length` == 2
* 1 <= $winner_i$, $loser_i$ <= $10^5$
* $winner_i$ != $loser_i$
* All `matches[i]` are **unique**.

### 解答

#### Javascript

function findWinners(matches) {
  const NL = [];
  const oneLoss = [];
  const lossCount = [];
  for (const [winner, loser] of matches) {
    if (!lossCount[winner]) {
      lossCount[winner] = 0;
    }
    if (!lossCount[loser]) {
      lossCount[loser] = 1;
    } else {
      lossCount[loser]++;
    }
  }

  for (let i = 1; i < lossCount.length; i++) {
    if (lossCount[i] === 0) {
      NL.push(i);
    } else if (lossCount[i] === 1) {
      oneLoss.push(i);
    }
  }

  return [NL, oneLoss];
}

> Time complexity : $O(n+k)$
> 這裡k最大為`lossCount.length`是100000
> [name=Marsgoat] [time= Nov 28, 2022]

#### C++

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        int counts[100001] = {0};
        for (int i = 0; i < matches.size(); i++) {
            counts[matches[i][0]] |= 1;
            counts[matches[i][1]] += 2;
        }
        vector<vector<int>> ans(2);
        for (int i = 1; i <= 100000; i++) {
            int c = counts[i];
            if (c == 0) continue;
            if (c == 1) ans[0].push_back(i);
            if (c == 2 || c == 3) ans[1].push_back(i);
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Mon, Nov 28]

#### Python

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        winners = [winner for winner, _ in matches]
        losers = [loser for _, loser in matches]
        ans = [sorted(set(winners) - set(losers))]

        counter = Counter(losers)
        ans.append(sorted([loser for loser, times in counter.items() if times == 1]))
        return ans

> [name=Yen-Chi Chen][time=Mon, Nov 28]

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        res = []
        winners = []
        losers = []
        ht = {}
        
        for winner, loser in matches:
            ht[winner] = ht.get(winner, 0)
            ht[loser] = ht.get(loser, 0) + 1
            
        for key, val in ht.items():
            if val == 0:
                winners.append(key)
            elif val == 1:
                losers.append(key)
                
        return [sorted(winners), sorted(losers)]

> [name=Kobe Bryant][time=Mon, Nov 28]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)