3160.md

title	description	keywords
3160. 所有球里面不同颜色的数目	LeetCode 3160. 所有球里面不同颜色的数目题解，Find the Number of Distinct Colors Among the Balls，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 3160. 所有球里面不同颜色的数目 所有球里面不同颜色的数目 Find the Number of Distinct Colors Among the Balls 解题思路 数组 哈希表 模拟

3160. 所有球里面不同颜色的数目

🟠 Medium  🔖  数组 哈希表 模拟  🔗 力扣 LeetCode

题目

You are given an integer limit and a 2D array queries of size n x 2.

There are limit + 1 balls with distinct labels in the range [0, limit]. Initially, all balls are uncolored. For every query in queries that is of the form [x, y], you mark ball x with the color y. After each query, you need to find the number of distinct colors among the balls.

Return an array result of length n, where result[i] denotes the number of distinct colors after ith query.

Note that when answering a query, lack of a color will not be considered as a color.

Example 1:

Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]

Output: [1,2,2,3]

Explanation:

• After query 0, ball 1 has color 4.
• After query 1, ball 1 has color 4, and ball 2 has color 5.
• After query 2, ball 1 has color 3, and ball 2 has color 5.
• After query 3, ball 1 has color 3, ball 2 has color 5, and ball 3 has color 4.

Example 2:

Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]

Output: [1,2,2,3,4]

Explanation:

• After query 0, ball 0 has color 1.
• After query 1, ball 0 has color 1, and ball 1 has color 2.
• After query 2, ball 0 has color 1, and balls 1 and 2 have color 2.
• After query 3, ball 0 has color 1, balls 1 and 2 have color 2, and ball 3 has color 4.
• After query 4, ball 0 has color 1, balls 1 and 2 have color 2, ball 3 has color 4, and ball 4 has color 5.

Constraints:

• 1 <= limit <= 10^9
• 1 <= n == queries.length <= 10^5
• queries[i].length == 2
• 0 <= queries[i][0] <= limit
• 1 <= queries[i][1] <= 10^9

题目大意

给你一个整数 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 <= 10^9
• 1 <= n == queries.length <= 10^5
• queries[i].length == 2
• 0 <= queries[i][0] <= limit
• 1 <= queries[i][1] <= 10^9

解题思路

1. 初始化: 定义两个 Map 和结果数组 res。

   • ballMap: 存储每个球当前的颜色，用于追踪每个球的最新状态。
   • colorMap: 记录每种颜色出现的球数量，用于维护不同颜色的数量。

2. 遍历查询:

   • 如果 ballMap 中已经存在该球编号：
     • 获取该球的之前颜色 prevColor。
     • 更新 colorMap 中对应颜色的计数，若计数为 0 则删除该颜色。
   • 将新颜色写入 ballMap 并更新 colorMap 计数。

3. 记录结果: 将 colorMap.size 追加到结果数组中。

复杂度分析

• 时间复杂度: O(n)，其中 n 为查询的数量，每个查询操作都在 Map 中完成，时间复杂度为 O(1)。
• 空间复杂度: O(n)，用于存储球和颜色的映射关系。

代码

/**
 * @param {number} limit
 * @param {number[][]} queries
 * @return {number[]}
 */
var queryResults = function (limit, queries) {
	let ballMap = new Map();
	let colorMap = new Map();
	let res = [];

	for (let [ball, color] of queries) {
		const prevColor = ballMap.get(ball);

		// 如果颜色发生变化
		if (prevColor !== undefined) {
			const prevCount = colorMap.get(prevColor);
			if (prevCount === 1) {
				colorMap.delete(prevColor);
			} else {
				colorMap.set(prevColor, prevCount - 1);
			}
		}

		// 更新 ballMap 和 colorMap
		ballMap.set(ball, color);
		colorMap.set(color, (colorMap.get(color) || 0) + 1);

		res.push(colorMap.size);
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
1742	盒子中小球的最大数量	[✓]	哈希表 数学 计数	🟢	🀄️ 🔗