3238. 求出胜利玩家的数目 作者: zorth 时间: 2024-11-23 分类: 算法 简单题 | 数组 | 给你一个整数 `n` ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 `pick` ，其中 `pick[i] = [xi, yi]` 表示玩家 `xi` 获得了一个颜色为 `yi` 的球。 如果玩家 `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 <= xi <= n - 1 ` - `0 <= yi <= 10` --- 刚上来的时候觉得可能是要用哈希表，还顺带复习了一下哈希表的相关知识： ```java // Creating a HashMap HashMap<KeyType, ValueType> map = new HashMap<>(); // Adding elements map.put(key, value); // Getting values ValueType value = map.get(key); // Removing elements map.remove(key); // Checking if key exists boolean exists = map.containsKey(key); ``` 实际上，从哈希表的角度来想，太复杂了，针对每一个玩家都要进行一遍哈希表的对比，时间复杂度上、空间复杂度上来说，都太高了。 不得已看了题解，题解巧妙的地方在于把任务拆解了，因为提示里提到颜色的范围是大于0小于10的，所以至多有11个颜色，如果创建一个二维数组，每一行代表每一个用户，每一列代表每一个颜色，然后遍历pick数组，他的每一个数值出现时，在二维数组上对应坐标加一。 最后问题会变成一个简单的二维数组遍历问题。 ```java class Solution { public int winningPlayerCount(int n, int[][] pick) { int cnt[][] = new int[n][11]; for (int[] p : pick) { cnt[p[0]][p[1]]++; } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 11; j++) { if (cnt[i][j] > i) { ans++; break; } } } return ans; } } ``` --- 这里带上官方的题解： 首先我们需要统计每个玩家得到的每种颜色的球的数目，此时需要遍历 数组 pick。由于颜色 y 的取值范围为 [0,10]，此时我们用一个 n×11 的二维数组统计每个玩家得到的每种颜色的球的数目。然后我们从 0 到 n−1 依次遍历每个玩家，如果d当前第 i 个玩家至少有一种颜色的球大于玩家编号 i，则胜利玩家数目加 1，返回总的胜利玩家数目即可。 标签: none
