2023-06-18：给定一个长度为N的一维数组scores，代表0～N-1号员工的初始得分，scores【i】＝a，

2023-06-18：给定一个长度为N的一维数组scores, 代表0~N-1号员工的初始得分，

scores[i] = a, 表示i号员工一开始得分是a，

给定一个长度为M的二维数组operations,

operations[i] = 。

表示第i号操作为 :

如果a==1, 表示将目前分数

如果a==2, 表示将编号为b的员工，分数改成c，

所有操作从0~M-1, 依次发生。

返回一个长度为N的一维数组ans，表示所有操作做完之后，每个员工的得分是多少。

1

1

0

来自TikTok美国笔试。

答案2023-06-18：

具体步骤如下：

1.创建一个长度为N的一维数组，表示每个员工的初始得分。

2.创建一个长度为M的二维数组，表示操作序列。

3.定义一个函数来处理操作序列。

4.初始化一个节点数组，用于存储每个员工的节点信息。

5.初始化一个空的得分和桶的映射表。

6.遍历数组，为每个得分值创建一个桶，并将对应的员工节点添加到桶中。

7.遍历数组，处理每个操作。

8.对于类型为1的操作，获取小于当前得分的最大得分值，然后将它们的桶合并到新的得分值对应的桶中。

9.对于类型为2的操作，获取该员工节点，并将其从原来的桶中移除，然后添加到新的得分值对应的桶中。

10.遍历得分和桶的映射表，将桶中的员工节点按照顺序取出，更新到结果数组中。

11.返回最终的结果数组。

12.进行功能测试和性能测试。

时间复杂度分析：

• 遍历数组并创建桶，时间复杂度为O(N)。

• 遍历数组，每个操作的时间复杂度为O(logN)（由于使用了有序映射表来实现桶，检索操作的时间复杂度为O(logN)）。

• 遍历得分和桶的映射表，每个桶中的员工节点数量为O(1)，遍历的时间复杂度为O(N)。

• 总体时间复杂度为O(N + KlogN)，其中K为操作序列的长度。

空间复杂度分析：

• 创建一个长度为N的数组，空间复杂度为O(N)。

• 创建一个长度为M的数组，空间复杂度为O(M)。

• 创建一个长度为N的节点数组，空间复杂度为O(N)。

• 创建一个有序映射表，储存每个得分值对应的桶，空间复杂度为O(N)。

• 结果数组的长度为N，空间复杂度为O(N)。

• 总体空间复杂度为O(N + M)。

go完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述