2025-03-16：求出胜利玩家的数目。用go语言，给定一个整数 n，表示游戏中的玩家数量，以及一个二维整数数组 pick，其中每个元素 pick[i] = [xi, yi] 表示玩家 xi 获得了一种颜色为 yi 的球。

在这个游戏中，若某个玩家拥有的任一种颜色的球的数量严格超过他们的编号（即玩家 i 的编号是 i），那么我们称该玩家为“胜利玩家”。具体而言：

1.玩家 0 只需拥有任何球便可视为胜利玩家。

2.玩家 1 必须至少拥有 2 个相同颜色的球才能被视为胜利玩家。

3.玩家 2 必须拥有至少 3 个相同颜色的球，依此类推。

最终，要求计算出游戏中胜利玩家的总数量。

通过这种方式，可能会有多个玩家被认定为胜利玩家。

2 <= n <= 10。

1 <= pick.length <= 100。

pick[i].length == 2。

0 <= xi <= n - 1 。

0 <= yi <= 10。

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

输出：2。

解释：

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

题目来自leetcode3238。

大体步骤如下：

1.创建一个二维数组 cnt 用于统计每个玩家拥有的不同颜色的球的数量。

2.遍历 pick 数组，更新 cnt 数组中对应玩家和颜色的数量。

3.遍历 cnt 数组，判断每个玩家是否为“胜利玩家”：

• 若某种颜色的球数量大于玩家的编号，该玩家满足“胜利玩家”的条件，计数器加一。

• 若玩家 0 只需拥有任何球即视为胜利玩家；其他玩家需拥有的相同颜色球数量逐渐递增。

总结与复杂度分析：

1.时间复杂度：

• 统计玩家拥有的球的数量需要遍历 pick 数组，所以是 O(N) 的复杂度。

• 判断胜利玩家也需要遍历 cnt 二维数组，总共是 n * 11 个元素，时间复杂度为 O(N)。

• 因此总体时间复杂度为 O(N)。

2.额外空间复杂度：

• 创建了一个二维数组 cnt 用于统计球数量，大小为 n * 11，额外空间复杂度为 O(N)。

Go完整代码如下：

package main

import (
	"fmt"
)

func winningPlayerCount(n int, pick [][]int) int {
	cnt := make([][]int, n)
	for i := range cnt {
		cnt[i] = make([]int, 11)
	}
	for _, p := range pick {
		cnt[p[0]][p[1]]++
	}

	ans := 0
	for i := 0; i < n; i++ {
		for j := 0; j <= 10; j++ {
			if cnt[i][j] > i {
				ans++
				break
			}
		}
	}
	return ans
}

func main() {
	n := 4
	pick := [][]int{{0, 0}, {1, 0}, {1, 0}, {2, 1}, {2, 1}, {2, 0}}
	result := winningPlayerCount(n, pick)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def winning_player_count(n, pick):
    # 创建统计数组
    cnt = [[0] * 11 for _ in range(n)]
    
    # 统计每个玩家获得各颜色球的数量
    for p in pick:
        cnt[p[0]][p[1]] += 1

    ans = 0
    # 检查每个玩家是否是胜利玩家
    for i in range(n):
        for j in range(11):
            if cnt[i][j] > i:
                ans += 1
                break
    return ans

if __name__ == "__main__":
    n = 4
    pick = [[0, 0], [1, 0], [1, 0], [2, 1], [2, 1], [2, 0]]
    result = winning_player_count(n, pick)
    print(result)