2023-06-18：给定一个长度为N的一维数组scores, 代表0~N-1号员工的初始得分， scores[i] = a, 表示i号员工一开始得分是a，给定一个长度为M的二维数组operatio - 服务器托管|北京服务器租用|机房托管租用|IDC托管租用|机房机柜带宽租用-价格及费用咨询

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，表示所有操作做完之后，每个员工的得分是多少。

来自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)。

go完整代码如下：

package main

import (
	"fmt"
	"math/rand"
	"time"
)

// 桶，得分在有序表里！桶只作为有序表里的value，不作为key
type Bucket struct {
	head *Node
	tail *Node
}

func NewBucket() *Bucket {
	head := &Node{index: -1}
	tail := &Node{index: -1}
	head.next = tail
	tail.last = head
	return &Bucket{head: head, tail: tail}
}

func (b *Bucket) add(node *Node) {
	node.last = b.tail.last
	node.next = b.tail
	b.tail.last.next = node
	b.tail.last = node
}

func (b *Bucket) merge(join *Bucket) {
	if join.head.next != join.tail {
		b.tail.last.next = join.head.next
		join.head.next.last = b.tail.last
		join.tail.last.next = b.tail
		b.tail.last = join.tail.last
		join.head.next = join.tail
		join.tail.last = join.head
	}
}

// Node represents a node in the bucket
type Node struct {
	index int
	last  *Node
	next  *Node
}

func (n *Node) connectLastNext() {
	n.last.next = n.next
	n.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  b {
		return a
	}
	return b
}

// RandomScores generates an array of random scores
func randomScores(n, v int) []int {
	scores := make([]int, n)
	rand.Seed(time.Now().UnixNano())
	for i := 0; i

c++完整代码如下：

#include 
#include 
#include 
#include 
#include 

using namespace std;

class Bucket;

// Node represents a node in the bucket
class Node {
public:
    int index;
    Node* last;
    Node* next;

    void connectLastNext() {
        last->next = next;
        next->last = last;
    }
};

// Bucket, scores stored in a sorted list
class Bucket {
public:
    Node* head;
    Node* tail;

    Bucket() {
        head = new Node();
        tail = new Node();
        head->index = -1;
        tail->index = -1;
        head->next = tail;
        tail->last = head;
    }

    void add(Node* node) {
        node->last = tail->last;
        node->next = tail;
        tail->last->next = node;
        tail->last = node;
    }

    void merge(Bucket* join) {
        if (join->head->next != join->tail) {
            tail->last->next = join->head->next;
            join->head->next->last = tail->last;
            join->tail->last->next = tail;
            tail->last = join->tail->last;
            join->head->next = join->tail;
            join->tail->last = join->head;
        }
    }
};

vector operateScores1(const vector& scores, const vector>& operations) {
    int n = scores.size();
    vector ans(scores);

    for (const auto& op : operations) {
        if (op[0] == 1) {
            for (int i = 0; i & m, int target);

vector operateScores2(const vector& scores, const vector>& operations) {
    int n = scores.size();
    vector nodes(n);
    map scoreBucketMap;

    for (int i = 0; i index = i;
        if (scoreBucketMap.find(scores[i]) == scoreBucketMap.end()) {
            scoreBucketMap[scores[i]] = new Bucket();
        }
        scoreBucketMap[scores[i]]->add(nodes[i]);
    }

    for (const auto& op : operations) {
        if (op[0] == 1) {
            int floorKeyV = floorKey(scoreBucketMap, op[1] - 1);

            if (floorKeyV != -1 && scoreBucketMap.find(op[1]) == scoreBucketMap.end()) {
                scoreBucketMap[op[1]] = new Bucket();
            }

            while (floorKeyV != -1) {
                scoreBucketMap[op[1]]->merge(scoreBucketMap[floorKeyV]);
                scoreBucketMap.erase(floorKeyV);
                floorKeyV = floorKey(scoreBucketMap, op[1] - 1);
            }
        }
        else {
            Node* cur = nodes[op[1]];
            cur->connectLastNext();

            if (scoreBucketMap.find(op[2]) == scoreBucketMap.end()) {
                scoreBucketMap[op[2]] = new Bucket();
            }

            scoreBucketMap[op[2]]->add(cur);
        }
    }

    vector ans(n);
    for (const auto& entry : scoreBucketMap) {
        int score = entry.first;
        Bucket* bucket = entry.second;
        Node* cur = bucket->head->next;
        while (cur != bucket->tail) {
            ans[cur->index] = score;
            cur = cur->next;
        }
    }

    return ans;
}

int floorKey(const map& m, int target) {
    for (const auto& entry : m) {
        int score = entry.first;
        if (score  scores(n);
        vector> operations(m, vector(3));

        for (int j = 0; j  ans1 = operateScores1(scores, operations);
        vector ans2 = operateScores2(scores, operations);

        if (ans1 != ans2) {
            cout  scores(n);
    vector> operations(m, vector(3));

    for (int i = 0; i

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: Debug和release的介绍以及二者的区别

一、介绍 Debug 通常称为调试版本，它包含调试信息，并且不作任何优化，便于程序员调试程序。在Debug环境下，我们可以使用调试技巧，如观察监视、内存、反汇编等等。 Release 称为发布版本，它往往是进行了各种优化，使得程序在代码大小和运行速度上都是最优…

具体步骤如下：

go完整代码如下：

c++完整代码如下：

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用