2225.Find Players With Zero or One Losses

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

2225. 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

$winne{r}_i$ defeated player

$lose{r}_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 <=
  $winne{r}_i$,
  $lose{r}_i$ <=
  ${10}^5$
• $winne{r}_i$ !=
  $lose{r}_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
Marsgoat 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;
    }
};

Yen-Chi ChenMon, 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

Yen-Chi ChenMon, 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)]

Kobe BryantMon, Nov 28

Reference

回到題目列表