2024-12-30：所有球里面不同颜色的数目。用go语言，给定一个整数 limit 和一个大小为 n x 2 的二维数组 qu

福大大架构师每日一题

发布于 2024-12-30 15:55:54

6100

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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 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;

fnquery_results(_limit:i32, queries:Vec<(i32,i32)>)->Vec<i32>{
letmut ans=vec![0; queries.len()];
letmut color:HashMap<i32,i32>=HashMap::new();
letmut cnt:HashMap<i32,i32>=HashMap::new();

for(i, q)in queries.iter().enumerate(){
let(x, y)=*q;

// 如果已经有颜色 c，先减少其计数
ifletSome(&c)= color.get(&x){
letcount= 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()asi32;
}

    ans
}

fnmain(){
letlimit=4;
letqueries=vec![(1,4),(2,5),(1,3),(3,4)];
letresult=query_results(limit, queries);
println!("{:?}", result);
}