3238.求出胜利玩家的数目

【LetMeFly】3238.求出胜利玩家的数目：哈希表计数

力扣题目链接：https://leetcode.cn/problems/find-the-number-of-winning-players/

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

如果玩家 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 <= xi <= n - 1
• 0 <= yi <= 10

解题方法：(哈希表)计数

使用一个哈希表（数组也可以）记录每个玩家每种颜色的球的获得个数，遍历一遍pick数组即可完成统计。

然后对于每个玩家，从0到10遍历每种颜色的球的数量，一旦大于玩家编号，就答案加一且快进到下一个玩家。

• 时间复杂度$O(nC+len(pick))$，其中$C=11$代表11种颜色
• 空间复杂度$O(nC)$，若不想创建动态数组也可以创建$NC$大小的固定数组（其中$N=\max(n)=10$）

AC代码

C++

class Solution {
public:
    int winningPlayerCount(int n, vector<vector<int>>& pick) {
        int cnt[10][11] = {0};
        for (vector<int>& p : pick) {
            cnt[p[0]][p[1]]++;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 11; j++) {
                if (cnt[i][j] > i) {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
};

Python

from typing import List

class Solution:
    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int:
        cnt = [[0] * 11 for _ in range(n)]
        for a, b in pick:
            cnt[a][b] += 1
        return sum(any(cnt[i][j] > i for j in range(11)) for i in range(n))

Java

class Solution {
    public int winningPlayerCount(int n, int[][] pick) {
        int cnt[][] = new int[n][11];
        for (int[] p : pick) {
            cnt[p[0]][p[1]]++;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 11; j++) {
                if (cnt[i][j] > i) {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
}

Go

package main

func winningPlayerCount(n int, pick [][]int) (ans int) {
    cnt := make([][]int, n)
    for th := range cnt {
        cnt[th] = make([]int, 11)
    }
    for _, p := range pick {
        cnt[p[0]][p[1]]++
    }
    for i, row := range cnt {
        for _, val := range row {
            if val > i {
                ans++
                break
            }
        }
    }
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143995245