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

🟠 🔖 数组 哈希表 模拟 🔗 力扣open in new window LeetCodeopen in new window

题目

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

解题思路

初始化: 定义两个 Map 和结果数组 res。
- ballMap: 存储每个球当前的颜色，用于追踪每个球的最新状态。
- colorMap: 记录每种颜色出现的球数量，用于维护不同颜色的数量。
遍历查询:
- 如果 ballMap 中已经存在该球编号：
  - 获取该球的之前颜色 prevColor。
  - 更新 colorMap 中对应颜色的计数，若计数为 0 则删除该颜色。
- 将新颜色写入 ballMap 并更新 colorMap 计数。
记录结果: 将 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;
};

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

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

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目