3238. 求出胜利玩家的数目

题目描述

给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [x_i, y_i] 表示玩家 x_i 获得了一个颜色为 y_i 的球。

如果玩家 i 获得的球中任何一种颜色球的数目 严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：

如果玩家 0 获得了任何的球，那么玩家 0 是胜利玩家。
如果玩家 1 获得了至少 2 个相同颜色的球，那么玩家 1 是胜利玩家。
...
如果玩家 i 获得了至少 i + 1 个相同颜色的球，那么玩家 i 是胜利玩家。

请你返回游戏中 胜利玩家 的数目。

注意，可能有多个玩家是胜利玩家。

示例 1：

输入：n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]

输出：2

解释：

玩家 0 和玩家 1 是胜利玩家，玩家 2 和玩家 3 不是胜利玩家。

示例 2：

输入：n = 5, pick = [[1,1],[1,2],[1,3],[1,4]]

输出：0

解释：

没有胜利玩家。

示例 3：

输入：n = 5, pick = [[1,1],[2,4],[2,4],[2,4]]

输出：1

解释：

玩家 2 是胜利玩家，因为玩家 2 获得了 3 个颜色为 4 的球。

提示：

2 <= n <= 10
1 <= pick.length <= 100
pick[i].length == 2
0 <= x_i <= n - 1
0 <= y_i <= 10

解法

方法一：计数

我们可以用一个二维数组 $\textit{cnt}$ 记录每个玩家获得的每种颜色球的数量，用一个哈希表 $\textit{s}$ 记录胜利玩家的编号。

遍历 $\textit{pick}$ 数组，对于每个元素 $[x, y]$，我们将 $\textit{cnt}[x][y]$ 加一，如果 $\textit{cnt}[x][y]$ 大于 $x$，则将 $x$ 加入哈希表 $\textit{s}$。

最后返回哈希表 $\textit{s}$ 的大小即可。

时间复杂度 $O(m + n \times M)$，空间复杂度 $O(n \times M)$。其中 $m$ 为 $\textit{pick}$ 数组的长度，而 $n$ 和 $M$ 分别为玩家数目和颜色数目。

Python3JavaC++GoTypeScript

class Solution:
    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int:
        cnt = [[0] * 11 for _ in range(n)]
        s = set()
        for x, y in pick:
            cnt[x][y] += 1
            if cnt[x][y] > x:
                s.add(x)
        return len(s)

class Solution {
    public int winningPlayerCount(int n, int[][] pick) {
        int[][] cnt = new int[n][11];
        Set<Integer> s = new HashSet<>();
        for (var p : pick) {
            int x = p[0], y = p[1];
            if (++cnt[x][y] > x) {
                s.add(x);
            }
        }
        return s.size();
    }
}

class Solution {
public:
    int winningPlayerCount(int n, vector<vector<int>>& pick) {
        int cnt[10][11]{};
        unordered_set<int> s;
        for (const auto& p : pick) {
            int x = p[0], y = p[1];
            if (++cnt[x][y] > x) {
                s.insert(x);
            }
        }
        return s.size();
    }
};

func winningPlayerCount(n int, pick [][]int) int {
    cnt := make([][11]int, n)
    s := map[int]struct{}{}
    for _, p := range pick {
        x, y := p[0], p[1]
        cnt[x][y]++
        if cnt[x][y] > x {
            s[x] = struct{}{}
        }
    }
    return len(s)
}

function winningPlayerCount(n: number, pick: number[][]): number {
    const cnt: number[][] = Array.from({ length: n }, () => Array(11).fill(0));
    const s = new Set<number>();
    for (const [x, y] of pick) {
        if (++cnt[x][y] > x) {
            s.add(x);
        }
    }
    return s.size;
}

3238. 求出胜利玩家的数目

题目描述

解法

方法一：计数

评论