What is the primary pattern used in the "Find the Number of Winning Players" problem?

The problem follows the pattern of array scanning combined with hash lookup for efficient counting of picked balls by players.

How do I count the number of balls each player picks of a color?

You can use a hash table where the key is the color and the value is the count of balls picked by the player for that color.

How can I optimize this problem if there are many players or picks?

The problem can be optimized by using a hash map for fast lookups and updating counts efficiently during the scanning process.

What is the time complexity of the "Find the Number of Winning Players" problem?

The time complexity is O(n * k), where n is the number of players and k is the average number of picks per player.

What should I be careful about when implementing the solution?

Be careful about correctly counting the number of balls each player picks and ensuring that you compare it to their index properly.

#3238

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

求出胜利玩家的数目

给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [x i , y i ] 表示玩家 x i 获得了一个颜色为 y i 的球。如果玩家 i 获得的球中任何一种颜色球的数目严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：如…

数组哈希表计数

题目描述

给你一个整数 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

lightbulb

解题思路

方法一：计数

我们可以用一个二维数组 $\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$ 分别为玩家数目和颜色数目。

1

2

3

4

5

6

7

8

9

10

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for the candidate's ability to efficiently implement a hash-based solution to count occurrences.
question_mark
Evaluating if the candidate can handle the logic for counting and comparing player's index with ball counts.
question_mark
Checking if the candidate can optimize the solution using an array scanning technique and hash map updates.

warning

常见陷阱

外企场景

error
Forgetting to properly compare the count of balls for each color to the player's index.
error
Incorrectly handling the mapping between players and their ball picks, leading to errors in counting.
error
Failing to account for players who pick multiple balls of the same color and how to store and compare these counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem to work with more than one ball color, where players must pick a combination of colors to win.
arrow_right_alt
Extend the problem by allowing players to pick balls in multiple rounds and requiring a comparison of rounds.
arrow_right_alt
Introduce a constraint where a player must win in multiple categories (e.g., both a minimum number of total balls and a particular color count).

help

常见问题

外企场景

继续练习

#3265 统计近似相等数对 I #3267 统计近似相等数对 II #3186 施咒的最大总伤害