Easy

题目描述

给你一个整数 n，表示游戏中玩家的数量，以及一个二维数组 pick，其中 pick[i] = [xi, yi] 表示玩家 xi 拾取了一个颜色为 yi 的球。

如果玩家 i 拾取了严格超过 i 个相同颜色的球，那么玩家 i 获胜。换句话说：

  • 玩家 0 拾取任意一个球就获胜
  • 玩家 1 拾取至少 2 个相同颜色的球就获胜
  • …
  • 玩家 i 拾取至少 i + 1 个相同颜色的球就获胜

返回获胜玩家的数量。

注意多个玩家可以获胜。

示例 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 通过拾取 3 个颜色为 4 的球获胜。

提示：

  • 2 <= n <= 10
  • 1 <= pick.length <= 100
  • pick[i].length == 2
  • 0 <= xi <= n - 1
  • 0 <= yi <= 10

解题思路

这道题需要统计每个玩家拾取每种颜色球的数量，然后判断是否满足获胜条件。

解题思路：

  1. 数据统计：使用哈希表记录每个玩家拾取每种颜色球的数量。可以用二维数组或者嵌套哈希表来实现。

  2. 获胜条件判断：对于玩家 i，需要检查是否存在某种颜色的球，其拾取数量严格大于 i（即至少 i+1 个）。

  3. 遍历检查：遍历所有玩家，对每个玩家检查其拾取的所有颜色中是否有满足获胜条件的。

算法步骤：

  • 创建二维计数数组 count[player][color] 记录每个玩家拾取每种颜色的球数
  • 遍历 pick 数组，统计每个操作
  • 对每个玩家，检查是否存在某种颜色的球数量 > 玩家编号
  • 统计获胜玩家数量

由于数据规模很小（n≤10，颜色≤10），直接使用二维数组是最简洁高效的方法。

代码实现

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

class Solution:
    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int:
        count = [[0] * 11 for _ in range(n)]
        
        for player, color in pick:
            count[player][color] += 1
        
        winners = 0
        for i in range(n):
            for color in range(11):
                if count[i][color] > i:
                    winners += 1
                    break
        
        return winners

public class Solution {
    public int WinningPlayerCount(int n, int[][] pick) {
        int[,] count = new int[n, 11];
        
        foreach (var p in pick) {
            count[p[0], p[1]]++;
        }
        
        int winners = 0;
        for (int i = 0; i < n; i++) {
            for (int color = 0; color <= 10; color++) {
                if (count[i, color] > i) {
                    winners++;
                    break;
                }
            }
        }
        
        return winners;
    }
}

var winningPlayerCount = function(n, pick) {
    const count = Array.from({ length: n }, () => Array(11).fill(0));
    
    for (const [player, color] of pick) {
        count[player][color]++;
    }
    
    let winners = 0;
    for (let i = 0; i < n; i++) {
        for (let color = 0; color <= 10; color++) {
            if (count[i][color] > i) {
                winners++;
                break;
            }
        }
    }
    
    return winners;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m + n)m 是 pick 数组长度，n 是玩家数量。遍历 pick 数组需要 O(m)，检查每个玩家需要 O(n×11) = O(n)
空间复杂度O(n)需要 n×11 的二维数组存储计数信息

相关题目