问求职面试算法？

EN

请注意，对于每个操作，被投票支持的候选人的分数增加了整整一个。

这就打开了一个新的策略--而不是将一个候选人映射到它的分数，而是将一个分数映射到有这个分数的候选人列表中。

这可以很简单地实现为列表候选列表：(在模板，如语法：list<list<Candidate>>)。

此外，保持一个数组将每个候选数映射到实际Candidate元素的指针。

0的候选列表将在在O(1)中初始化数组的类似方式中隐式地设置为所有候选人。

• 投票时：

1. 你可以从推荐信中找到候选人: O(1)
2. 将其从当前列表中删除，并将其添加到下一个列表: O(1)
3. 要在Avoided()中支持O(r)：如果"0“列表中的元素数小于一半，则将其改为常规列表。
4. 如果表示分数的前一个元素现在没有候选项，则删除它，并将前一个分数直接链接到下一个得分(即，如果没有得分为3的候选元素，请连接2<->4)，这将确保O(n)空间，因为没有太多的空列表节点。

• 获得topK现在很容易，并且在O(k)中通过逐个迭代分数列表来完成(在输出k考生之后停止)
• 如果超过一半的候选项被避免，现在避免的是O(n) = O(r)，或者由于插入中的优化(3)而避免使用O(r)。

这里有一种可供选择的方法来实现Here ()。把两个号码和每一个被投票的人联系起来，开始运行和结束运行。最初，所有元素都被设置为None (可以通过O(1)数组初始化技巧来完成)。

当person m第一次被投票时，更新startOfRun和endOfRun数组：

if startOfRun[m-1] != None and startOfRun[m+1] == None
   endOfRun[startOfRun[m-1]] = m
else if startOfRun[m-1] == None and startOfRun[m+1] != None
   startOfRun[endOfRun[m+1]]
else if startOfRun[m-1] != None and startOfRun[m+1] != None
   endOfRun[startOfRun[m-1]] = endOfRun[m+1]
   startOfRun[endOfRun[m+1]] = startOfRun[m-1]
else
   startOfRun[m] = m
   endOfRun[m] = m

(为简洁而省略的边缘条件)。

现在你有很多被投票支持的人，你可以很容易地从一开始到每一次竞选结束。跑中的数字都是错误的，但我们并不在乎它们。有O(r)运行，所以您可以跳过所有在O(r)中投票赞成的人。

下面是实现受宠()的另一种方法。有两个数组，(1)按分数排序的扩展的人员数组，(2)从分数到第一个数组中的最后一个人的索引的映射，其得分不小于该值(如果没有这样的人，则为None)。最初，第一个数组是空的，第二个数组包含None的。

(array 1)
(index)       1 2 3 4 5 6 7 8 9
person        3 6 5 1 4 2 8 9 7
score         7 7 7 5 5 3 2 2 2

(array 2)
score         1 2 3 4 5 6 7 8 9
index in 1st  9 9 6 5 5 3 3 - -

一旦一个人第一次投票，它将被添加到数组的末尾，得分为1，并且更新array2[1]。一旦该人再次被投票，它将与具有相同分数的数组中的第一个人交换，得分增加，第二个数组被更新(我们只需要更新一个元素，对应于新分数的元素)。