3238. Find the Number of Winning Players

Problem

You are given an integer n representing the number of players in a game and a 2D array pick where pick[i] = [xᵢ, yᵢ] represents that the player xᵢ picked a ball of color yᵢ.

Player i wins the game if they pick strictly more than i balls of the same color. In other words,

• Player 0 wins if they pick any ball.
• Player 1 wins if they pick at least two balls of the same color.
• …
• Player i wins if they pick at leasti + 1 balls of the same color.

Return the number of players who win the game.

Note that multiple players can win the game.

https://leetcode.cn/problems/find-the-number-of-winning-players/

Example 1:

Input: n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]
Output: 2
Explanation:
Player 0 and player 1 win the game, while players 2 and 3 do not win.

Example 2:

Input: n = 5, pick = [[1,1],[1,2],[1,3],[1,4]]
Output: 0
Explanation:
No player wins the game.

Example 3:

Input: n = 5, pick = [[1,1],[2,4],[2,4],[2,4]]
Output: 1
Explanation:
Player 2 wins the game by picking 3 balls with color 4.

Constraints:

• 2 <= n <= 10
• 1 <= pick.length <= 100
• pick[i].length == 2
• 0 <= xᵢ <= n - 1
• 0 <= yᵢ <= 10

Test Cases

1
2

class Solution:
    def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import pytest

from solution import Solution


@pytest.mark.parametrize('n, pick, expected', [
    (4, [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]], 2),
    (5, [[1,1],[1,2],[1,3],[1,4]], 0),
    (5, [[1,1],[2,4],[2,4],[2,4]], 1),
])
class Test:
    def test_solution(self, n, pick, expected):
        sol = Solution()
        assert sol.winningPlayerCount(n, pick) == expected

Thoughts

时间复杂度 O(n + p)，空间复杂度 O(n * c)，其中 p 是 pick 的数量，c 是不同颜色的个数。

循环中可以适当裁剪，比如一个 player 已经是赢家，就不用再更新他的球的统计信息。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def winningPlayerCount(self, n: int, pick: list[list[int]]) -> int:
        win_count = 0
        # color_counts[i]: player i's ball color distribution.
        color_counts: list[dict[int, int]] = {i: {} for i in range(n)}
        max_picks = [0] * n # max_picks[i]: player i's largest count of balls of the same color.
        for i, c in pick:
            if max_picks[i] > i:
                continue

            counts = color_counts[i]
            counts[c] = cnt = counts.get(c, 0) + 1
            if cnt > max_picks[i]:
                max_picks[i] = cnt
                if cnt > i and (win_count := win_count + 1) == n:
                    break

        return win_count

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章