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：

chatgpt[1]

题目来自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 mainimport "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);}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP