当前位置: 首页 > 滚动

天天热推荐:2023-06-18:给定一个长度为N的一维数组scores, 代表0~N-1号员工的初始得分, scores[i] = a, 表示i号员工一开始得分是a, 给定一个长度为M的二维数组operatio

来源:博客园 发布时间:2023-06-18 18:15:03

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

go完整代码如下:
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("性能测试结束")}
c++完整代码如下:
#include #include #include #include #include using namespace std;class Bucket;// Node represents a node in the bucketclass Node {public:    int index;    Node* last;    Node* next;    void connectLastNext() {        last->next = next;        next->last = last;    }};// Bucket, scores stored in a sorted listclass 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 < n; i++) {                ans[i] = max(ans[i], op[1]);            }        }        else {            ans[op[1]] = op[2];        }    }    return ans;}int floorKey(const map& 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 < n; i++) {        nodes[i] = new Node();        nodes[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 <= target) {            return score;        }    }    return -1;}int main() {    int N = 1000;    int M = 1000;    int V = 100000;    int testTimes = 100;    cout << "功能测试开始" << endl;    for (int i = 0; i < testTimes; i++) {        int n = rand() % N + 1;        int m = rand() % M + 1;        vector scores(n);        vector> operations(m, vector(3));        for (int j = 0; j < n; j++) {            scores[j] = rand() % V;        }        for (auto& op : operations) {            if (rand() < 0.5) {                op[0] = 1;                op[1] = rand() % V;            }            else {                op[0] = 2;                op[1] = rand() % n;                op[2] = rand() % V;            }        }        vector ans1 = operateScores1(scores, operations);        vector ans2 = operateScores2(scores, operations);        if (ans1 != ans2) {            cout << "出错了!" << endl;        }    }    cout << "功能测试结束" << endl;    cout << "性能测试开始" << endl;    int n = 1000000;    int m = 1000000;    int v = 1000000000;    vector scores(n);    vector> operations(m, vector(3));    for (int i = 0; i < n; i++) {        scores[i] = rand() % v;    }    for (auto& op : operations) {        op[0] = rand() < 0.5 ? 1 : 2;        op[1] = rand() % n;        op[2] = rand() % v;    }    cout << "总人数: " << n << endl;    cout << "操作数: " << m << endl;    cout << "值范围: " << v << endl;    clock_t start = clock();    operateScores2(scores, operations);    clock_t end = clock();    cout << "运行时间: " << double(end - start) / CLOCKS_PER_SEC << endl;    cout << "性能测试结束" << endl;    return 0;}
标签:

Copyright   2015-2022 欧洲晨报网 版权所有  备案号:沪ICP备2022005074号-23   联系邮箱: 58 55 97 3@qq.com