本文最后更新于：2024年11月23日 下午
3238. 求出胜利玩家的数目
level: easy
tag:数组 哈希表 计数
给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [xi, yi] 表示玩家 xi 获得了一个颜色为 yi 的球。
如果玩家 i 获得的球中任何一种颜色球的数目 严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：
如果玩家 0 获得了任何的球，那么玩家 0 是胜利玩家。
如果玩家 1 获得了至少 2 个相同颜色的球，那么玩家 1 是胜利玩家。
…
如果玩家 i 获得了至少 i + 1 个相同颜色的球，那么玩家 i 是胜利玩家。
请你返回游戏中 胜利玩家 的数目。
注意，可能有多个玩家是胜利玩家。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
| 给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [xi, yi] 表示玩家 xi 获得了一个颜色为 yi 的球。
如果玩家 i 获得的球中任何一种颜色球的数目 严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：
如果玩家 0 获得了任何的球，那么玩家 0 是胜利玩家。
如果玩家 1 获得了至少 2 个相同颜色的球，那么玩家 1 是胜利玩家。
...
如果玩家 i 获得了至少 i + 1 个相同颜色的球，那么玩家 i 是胜利玩家。
请你返回游戏中 胜利玩家 的数目。
注意，可能有多个玩家是胜利玩家。
|
题解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| function winningPlayerCount(n: number, pick: number[][]): number {
const map = new Map();
const res = new Map();
pick.forEach((item) => {
if (map.has(item[0])) {
const obj = map.get(item[0]);
if (obj.hasOwnProperty(item[1])) {
++obj[item[1]];
} else {
obj[item[1]] = 1;
}
if (obj[item[1]] > item[0] && !res.has(item[0])) {
res.set(item[0], 1);
}
map.set(item[0], obj);
} else {
const key = item[1];
if (item[0] === 0) {
res.set(item[0], 1);
}
map.set(item[0], { [key]: 1 });
}
});
return res.size;
}
|
思路：
- 遍历数组，将每个玩家的球的颜色和数量存入 map 中,其中 key 为玩家 id，value 为对象，对象的 key 为球的颜色，value 为该颜色球的数量
- 判断每个玩家是否满足胜利条件，如果满足则存入 res 中，res 使用了 map 数据结构，避免重复统计
- 返回 res 的长度
复杂度
m 为 pick 数组的长度， n 为 结果的长度
时间复杂度：O(m)
空间复杂度：O(n+m)