2024-12-30：所有球里面不同颜色的数目。用go语言，给定一个整数 limit 和一个大小为 n x 2 的二维数组 queries，其中包含若干操作。
我们有 limit + 1 个球，它们的编号为 [0, limit]，每个球的编号都是独特的。
一开始，所有的球都是无色的。
每个操作的形式为 [x, y]，表示将球 x 染成颜色 y。
在每次操作后，我们需要计算并返回所有球中不同颜色的数量。
请返回一个长度为 n 的数组 result，该数组的第 i 个元素表示第 i 次操作后不同颜色的总数。
需要注意的是，没有染色的球不计入不同颜色的统计。
1 <= limit <= 1000000000。
1 <= n == queries.length <= 100000。
queries[i].length == 2。
0 <= queries[i][0] <= limit。
1 <= queries[i][1] <= 1000000000。
输入：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 。
答案2024-12-30：
题目来自leetcode3160。
大体步骤如下：
1.初始化一个空的结果数组 ans，用于存储每次操作后的不同颜色总数。
2.初始化两个空的映射表：color 用于记录球的颜色，cnt 用于记录每种颜色的球数量。
3.遍历操作数组 queries，对每个操作进行处理：
3.a. 获取操作中的球编号 x 和颜色 y。
3.b. 如果球 x 已经有颜色，更新颜色计数表 cnt，将之前记录的颜色数量减一，如果数量为0则从计数表中删除此颜色。
3.c. 更新球 x 的颜色为 y，同时更新颜色计数表 cnt 中相应颜色的球数量加一。
3.d. 将当前不同颜色的总数记录在结果数组 ans 中。
4.返回结果数组 ans。
总的时间复杂度取决于操作次数n和limit的数量，程序中需要遍历所有的操作，故时间复杂度为O(n)。额外空间复杂度主要由映射表 color 和 cnt 以及结果数组 ans 所占空间决定，因为这里的颜色数量是有限的，最坏情况下额外空间也是有限的，所以空间复杂度为O(1)。
Go完整代码如下：
package main
import "fmt"
func queryResults(_ int, queries [][]int) []int {
ans := make([]int, len(queries))
color := map[int]int{}
cnt := map[int]int{}
for i, q := range queries {
x, y := q[0], q[1]
if c := color[x]; c > 0 {
cnt[c]--
if cnt[c] == 0 {
delete(cnt, c)
}
}
color[x] = y
cnt[y]++
ans[i] = len(cnt)
}
return ans
}
func main() {
limit := 4
queries := [][]int{{1, 4}, {2, 5}, {1, 3}, {3, 4}}
result := queryResults(limit, queries)
fmt.Println(result)
}
Rust完整代码如下：
use std::collections::HashMap;
fn query_results(_limit: i32, queries: Vec<(i32, i32)>) -> Vec<i32> {
let mut ans = vec![0; queries.len()];
let mut color: HashMap<i32, i32> = HashMap::new();
let mut cnt: HashMap<i32, i32> = HashMap::new();
for (i, q) in queries.iter().enumerate() {
let (x, y) = *q;
// 如果已经有颜色 c，先减少其计数
if let Some(&c) = color.get(&x) {
let count = cnt.entry(c).or_insert(0);
*count -= 1;
if *count == 0 {
cnt.remove(&c);
}
}
// 更新颜色
color.insert(x, y);
// 增加新颜色 y 的计数
*cnt.entry(y).or_insert(0) += 1;
// 结果为当前不同颜色的数量
ans[i] = cnt.len() as i32;
}
ans
}
fn main() {
let limit = 4;
let queries = vec![(1, 4), (2, 5), (1, 3), (3, 4)];
let result = query_results(limit, queries);
println!("{:?}", result);
}
