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

【资料图】

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

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

operations[i] = {a, b, c}。

表示第i号操作为 :

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

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

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

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

1 <= N <= 10的6次方，

1 <= M <= 10的6次方，

0 <= 分数 <= 10的9次方。

来自TikTok美国笔试。

答案2023-06-18：

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

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

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

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

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

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

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

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

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

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

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

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

时间复杂度分析：

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

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

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

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

空间复杂度分析：

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

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

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

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

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

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

package mainimport ("fmt""math/rand""time")// 桶，得分在有序表里！桶只作为有序表里的value，不作为keytype Bucket struct {head *Nodetail *Node}func NewBucket() *Bucket {head := &Node{index: -1}tail := &Node{index: -1}head.next = tailtail.last = headreturn &Bucket{head: head, tail: tail}}func (b *Bucket) add(node *Node) {node.last = b.tail.lastnode.next = b.tailb.tail.last.next = nodeb.tail.last = node}func (b *Bucket) merge(join *Bucket) {if join.head.next != join.tail {b.tail.last.next = join.head.nextjoin.head.next.last = b.tail.lastjoin.tail.last.next = b.tailb.tail.last = join.tail.lastjoin.head.next = join.tailjoin.tail.last = join.head}}// Node represents a node in the buckettype Node struct {index intlast  *Nodenext  *Node}func (n *Node) connectLastNext() {n.last.next = n.nextn.next.last = n.last}// 暴力方法func operateScores1(scores []int, operations [][]int) []int {n := len(scores)ans := make([]int, n)copy(ans, scores)for _, op := range operations {if op[0] == 1 {for i := 0; i < n; i++ {ans[i] = max(ans[i], op[1])}} else {ans[op[1]] = op[2]}}return ans}// 正式方法func operateScores2(scores []int, operations [][]int) []int {n := len(scores)nodes := make([]*Node, n)scoreBucketMap := make(map[int]*Bucket)for i := 0; i < n; i++ {nodes[i] = &Node{index: i}if _, ok := scoreBucketMap[scores[i]]; !ok {scoreBucketMap[scores[i]] = NewBucket()}scoreBucketMap[scores[i]].add(nodes[i])}for _, op := range operations {if op[0] == 1 {floorKeyV := floorKey(scoreBucketMap, op[1]-1)if floorKeyV != -1 && scoreBucketMap[op[1]] == nil {scoreBucketMap[op[1]] = NewBucket()}for floorKeyV != -1 {scoreBucketMap[op[1]].merge(scoreBucketMap[floorKeyV])delete(scoreBucketMap, floorKeyV)floorKeyV = floorKey(scoreBucketMap, op[1]-1)}} else {cur := nodes[op[1]]cur.connectLastNext()if scoreBucketMap[op[2]] == nil {scoreBucketMap[op[2]] = NewBucket()}scoreBucketMap[op[2]].add(cur)}}ans := make([]int, n)for score, bucket := range scoreBucketMap {cur := bucket.head.nextfor cur != bucket.tail {ans[cur.index] = scorecur = cur.next}}return ans}func floorKey(m map[int]*Bucket, target int) int {for score := range m {if score <= target {return score}}return -1}func max(a, b int) int {if a > b {return a}return b}// RandomScores generates an array of random scoresfunc randomScores(n, v int) []int {scores := make([]int, n)rand.Seed(time.Now().UnixNano())for i := 0; i < n; i++ {scores[i] = rand.Intn(v)}return scores}// RandomOperations generates a 2D array of random operationsfunc randomOperations(n, m, v int) [][]int {operations := make([][]int, m)rand.Seed(time.Now().UnixNano())for i := 0; i < m; i++ {operations[i] = make([]int, 3)if rand.Float32() < 0.5 {operations[i][0] = 1operations[i][1] = rand.Intn(v)} else {operations[i][0] = 2operations[i][1] = rand.Intn(n)operations[i][2] = rand.Intn(v)}}return operations}// IsEqual checks if two arrays are equalfunc isEqual(arr1, arr2 []int) bool {if len(arr1) != len(arr2) {return false}for i := 0; i < len(arr1); i++ {if arr1[i] != arr2[i] {return false}}return true}// Main function for testingfunc main() {N := 1000M := 1000V := 100000testTimes := 100fmt.Println("功能测试开始")for i := 0; i < testTimes; i++ {n := rand.Intn(N) + 1m := rand.Intn(M) + 1scores := randomScores(n, V)operations := randomOperations(n, m, V)ans1 := operateScores1(scores, operations)ans2 := operateScores2(scores, operations)if !isEqual(ans1, ans2) {fmt.Println("出错了！")}}fmt.Println("功能测试结束")fmt.Println("性能测试开始")n := 100000m := 100000v := 100000000scores := randomScores(n, v)operations := randomOperations(n, m, v)fmt.Println("总人数:", n)fmt.Println("操作数:", n)fmt.Println("值范围:", v)start := time.Now()operateScores2(scores, operations)end := time.Now()fmt.Println("运行时间:", end.Sub(start))fmt.Println("性能测试结束")}

#include #include #include 

标签：