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

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