2023-06-18：給定一個長度為N的一維數(shù)組scores, 代表0~N-1號員工的初始得分，

scores[i] = a, 表示i號員工一開始得分是a，

給定一個長度為M的二維數(shù)組operations,

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

表示第i號操作為 :

如果a==1, 表示將目前分數(shù)<b的所有員工，分數(shù)改成b，c這個值無用，

如果a==2, 表示將編號為b的員工，分數(shù)改成c，

所有操作從0~M-1, 依次發(fā)生。

返回一個長度為N的一維數(shù)組ans，表示所有操作做完之后，每個員工的得分是多少。

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

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

0 <= 分數(shù) <= 10的9次方。

來自TikTok美國筆試。

答案2023-06-18：

具體步驟如下：

1.創(chuàng)建一個長度為N的一維數(shù)組scores，表示每個員工的初始得分。

2.創(chuàng)建一個長度為M的二維數(shù)組operations，表示操作序列。

3.定義一個函數(shù)operateScores2來處理操作序列。

4.初始化一個節(jié)點數(shù)組nodes，用于存儲每個員工的節(jié)點信息。

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

6.遍歷scores數(shù)組，為每個得分值創(chuàng)建一個桶，并將對應的員工節(jié)點添加到桶中。

7.遍歷operations數(shù)組，處理每個操作。

8.對于類型為1的操作，獲取小于當前得分的最大得分值floorKeyV，然后將它們的桶合并到新的得分值對應的桶中。

9.對于類型為2的操作，獲取該員工節(jié)點，并將其從原來的桶中移除，然后添加到新的得分值對應的桶中。

10.遍歷得分和桶的映射表scoreBucketMap，將桶中的員工節(jié)點按照順序取出，更新到結果數(shù)組ans中。

11.返回最終的結果數(shù)組ans。

12.進行功能測試和性能測試。

時間復雜度分析：

• ??遍歷scores數(shù)組并創(chuàng)建桶，時間復雜度為O(N)。

• ??遍歷operations數(shù)組，每個操作的時間復雜度為O(logN)（由于使用了有序映射表來實現(xiàn)桶，檢索操作的時間復雜度為O(logN)）。

• ??遍歷得分和桶的映射表scoreBucketMap，每個桶中的員工節(jié)點數(shù)量為O(1)，遍歷的時間復雜度為O(N)。

• ??總體時間復雜度為O(N + KlogN)，其中K為操作序列的長度。

空間復雜度分析：

• ??創(chuàng)建一個長度為N的數(shù)組scores，空間復雜度為O(N)。

• ??創(chuàng)建一個長度為M的數(shù)組operations，空間復雜度為O(M)。

• ??創(chuàng)建一個長度為N的節(jié)點數(shù)組nodes，空間復雜度為O(N)。

• ??創(chuàng)建一個有序映射表scoreBucketMap，儲存每個得分值對應的桶，空間復雜度為O(N)。

• ??結果數(shù)組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?<?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.next
????????for?cur?!=?bucket.tail?{
????????????ans[cur.index]?=?score
????????????cur?=?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?scores
func?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?operations
func?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]?=?1
????????????operations[i][1]?=?rand.Intn(v)
????????}?else?{
????????????operations[i][0]?=?2
????????????operations[i][1]?=?rand.Intn(n)
????????????operations[i][2]?=?rand.Intn(v)
????????}
????}
????return?operations
}

//?IsEqual?checks?if?two?arrays?are?equal
func?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?testing
func?main()?{
????N?:=?1000
????M?:=?1000
????V?:=?100000
????testTimes?:=?100
????fmt.Println("功能測試開始")
????for?i?:=?0;?i?<?testTimes;?i++?{
????????n?:=?rand.Intn(N)?+?1
????????m?:=?rand.Intn(M)?+?1
????????scores?:=?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?:=?100000
????m?:=?100000
????v?:=?100000000
????scores?:=?randomScores(n,?v)
????operations?:=?randomOperations(n,?m,?v)
????fmt.Println("總人數(shù):",?n)
????fmt.Println("操作數(shù):",?n)
????fmt.Println("值范圍:",?v)
????start?:=?time.Now()
????operateScores2(scores,?operations)
????end?:=?time.Now()
????fmt.Println("運行時間:",?end.Sub(start))
????fmt.Println("性能測試結束")
}


c++完整代碼如下：

#include?<iostream>
#include?<vector>
#include?<map>
#include?<random>
#include?<ctime>

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<int>?operateScores1(const?vector<int>&?scores,?const?vector<vector<int>>&?operations)?{
????int?n?=?scores.size();
????vector<int>?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<int,?Bucket*>&?m,?int?target);

vector<int>?operateScores2(const?vector<int>&?scores,?const?vector<vector<int>>&?operations)?{
????int?n?=?scores.size();
????vector<Node*>?nodes(n);
????map<int,?Bucket*>?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<int>?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<int,?Bucket*>&?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<int>?scores(n);
????????vector<vector<int>>?operations(m,?vector<int>(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<int>?ans1?=?operateScores1(scores,?operations);
????????vector<int>?ans2?=?operateScores2(scores,?operations);

????????if?(ans1?!=?ans2)?{
????????????cout?<<?"出錯了！"?<<?endl;
????????}
????}
????cout?<<?"功能測試結束"?<<?endl;

????cout?<<?"性能測試開始"?<<?endl;
????int?n?=?1000000;
????int?m?=?1000000;
????int?v?=?1000000000;
????vector<int>?scores(n);
????vector<vector<int>>?operations(m,?vector<int>(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?<<?"總人數(shù):?"?<<?n?<<?endl;
????cout?<<?"操作數(shù):?"?<<?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;
}