求职面试算法?

Question

更新：索蒙能否回答我对n.'代词'm.的回答的最后评论？

请注意：我之前问过这个问题，但它完全是一团糟，所以我以原始形式写了更多细节。

问题：

我正在管理N个参与者之间的投票系统(每个参与者从1到N索引)，我想支持以下功能：

1. Init(N) - 初始化数据结构。 -O(1)
2. 投票(j，i) - 将人 j 投票(正好 1)添加到结果表中 人 i - 不允许某人自己投票。 -O(1)
3. 选民(i) - 返回投票给i的人数。 -O(1)
4. 起源(j) - 返回人 j 给其他人的票数。 -O(1)
5. 受青睐(k) - 根据他们获得的票数打印排名靠前的参与者(按降序排列)。 -O(k)
避免() - 打印
6. 所有未获得任何投票的参与者。 -O(r) 其中 r 是打印参与者的数量

在这个问题中，空间复杂度应该是O(N)。

只允许使用数组和(双重)链表。

---

我做了什么？我很容易解决 1-4 只需声明一个大小为 N 且每个单元格包含 to 值的数组;got和sent.当i投票给j我增加j的获取值和i的发送值时。

我仍然不知道如何以所需的复杂性解决 5 和 6。

注意：我正在寻找算法/想法而不是实际代码。

Answer 1

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

这将打开一个新策略 - 不是将候选人映射到其分数，而是将分数映射到具有此分数的候选人列表。

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

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

带有 0 的候选列表最初将隐式设置为所有候选，就像在 O(1) 中初始化数组一样。

• 投票时：

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

• 现在，通过从头到尾迭代分数列表(在输出k候选人后停止)，获得 topK 很容易O(k)完成
• 如果超过一半的候选者被避免，则现在O(n) = O(r)避免，或者由于插入中的优化 (3) 而O(r)避免。

Answer 2

这是实现 Avoided() 的另一种方法。将两个数字与每个已投票的人相关联，即运行开始和运行结束。最初所有元素都设置为None(可以使用 O(1) 数组初始化技巧来完成)。

当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) 中投票的人。

---

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

(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]。一旦这个人再次被投票，它就会与数组中具有相同分数的第一个人交换，分数增加，第二个数组更新(我们只需要更新一个元素，即与新分数对应的元素)。