LeetCode 题解工作台
所有球里面不同颜色的数目
给你一个整数 limit 和一个大小为 n x 2 的二维数组 queries 。 总共有 limit + 1 个球，每个球的编号为 [0, limit] 中一个 互不相同 的数字。一开始，所有球都没有颜色。 queries 中每次操作的格式为 [x, y] ，你需要将球 x 染上颜色 y 。每次操…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们使用一个哈希表 记录每个球的颜色，使用一个哈希表 记录每种颜色的球的个数。 接下来，遍历数组 ，对于每个查询 $(x, y)$，我们将颜色 的球的个数加 ，然后判断球 是否已经染色，如果已经染色，我们将球 的颜色的球的个数减 ，如果减到 ，我们将其从哈希表 中移除。接下来，我们将球 的颜色更新为 ，并将当前哈希表 的大小加入答案数组。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数 limit 和一个大小为 n x 2 的二维数组 queries 。
总共有 limit + 1 个球，每个球的编号为 [0, limit] 中一个 互不相同 的数字。一开始，所有球都没有颜色。queries 中每次操作的格式为 [x, y] ，你需要将球 x 染上颜色 y 。每次操作之后，你需要求出所有球颜色的数目。
请你返回一个长度为 n 的数组 result ，其中 result[i] 是第 i 次操作以后颜色的数目。
注意 ，没有染色的球不算作一种颜色。
示例 1：
输入：limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
输出：[1,2,2,3]
解释：
- 操作 0 后，球 1 颜色为 4 。
- 操作 1 后，球 1 颜色为 4 ，球 2 颜色为 5 。
- 操作 2 后，球 1 颜色为 3 ，球 2 颜色为 5 。
- 操作 3 后，球 1 颜色为 3 ，球 2 颜色为 5 ，球 3 颜色为 4 。
示例 2：
输入：limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
输出：[1,2,2,3,4]
解释：
- 操作 0 后，球 0 颜色为 1 。
- 操作 1 后，球 0 颜色为 1 ，球 1 颜色为 2 。
- 操作 2 后，球 0 颜色为 1 ，球 1 和 2 颜色为 2 。
- 操作 3 后，球 0 颜色为 1 ，球 1 和 2 颜色为 2 ，球 3 颜色为 4 。
- 操作 4 后，球 0 颜色为 1 ，球 1 和 2 颜色为 2 ，球 3 颜色为 4 ，球 4 颜色为 5 。
提示：
1 <= limit <= 1091 <= n == queries.length <= 105queries[i].length == 20 <= queries[i][0] <= limit1 <= queries[i][1] <= 109
解题思路
方法一：双哈希表
我们使用一个哈希表 记录每个球的颜色，使用一个哈希表 记录每种颜色的球的个数。
接下来，遍历数组 ，对于每个查询 ，我们将颜色 的球的个数加 ，然后判断球 是否已经染色，如果已经染色，我们将球 的颜色的球的个数减 ，如果减到 ，我们将其从哈希表 中移除。接下来，我们将球 的颜色更新为 ，并将当前哈希表 的大小加入答案数组。
遍历结束后，返回答案数组即可。
时间复杂度 ，空间复杂度 ，其中 为数组 的长度。
class Solution:
def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
g = {}
cnt = Counter()
ans = []
for x, y in queries:
cnt[y] += 1
if x in g:
cnt[g[x]] -= 1
if cnt[g[x]] == 0:
cnt.pop(g[x])
g[x] = y
ans.append(len(cnt))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each query triggers a constant-time hash map update. Space complexity is O(n) due to storing ball-to-color and color-to-ball maps for all balls and queries. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Do you track the previous color when updating a ball to avoid double counting?
- question_mark
Can you maintain a reverse map from colors to sets of balls for constant-time distinct count?
- question_mark
How would your solution scale if the limit of balls is very large compared to the number of queries?
常见陷阱
外企场景- error
Failing to remove a ball from its previous color set leads to overcounting distinct colors.
- error
Iterating over all balls after each query instead of using hash maps causes timeouts on large n.
- error
Using only a ball-to-color map without a reverse color-to-ball map prevents efficient distinct color counting.
进阶变体
外企场景- arrow_right_alt
Count distinct colors only within a specified range of balls for each query.
- arrow_right_alt
Allow recoloring multiple balls at once in a single query and compute distinct colors after batch updates.
- arrow_right_alt
Track not only distinct color counts but also the most frequent color after each query.