2025-03-16：求出胜利玩家的数目。用go语言，给定一个整数 n，表示游戏中的玩家数量，以及一个二维整数数组 pick，其

福大大架构师每日一题

发布于 2025-03-17 17:09:45

10600

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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-*-

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

    ans = 0
    # 检查每个玩家是否是胜利玩家
    for i inrange(n):
        for j inrange(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)