data-structures - 如何将数据保存在数组中以便在 O(n) 时间内排序打印？

Question

在游戏中，用户可以在每个回合中将 1 添加到 n 个计数器(编号为 1,2,...,n)。对于这场比赛，他有:

• 返回计数器i 内容的函数counter(i)。在 O(1) 时间内。

• 增加i 计数器的函数add(i)。在 O(1) 时间内。

• 函数 print() 打印按计数器内容排序的 id，降序排列。在 O(n) 时间内。

如何在 O(n) 的地方实现这样的游戏？

我知道我应该将计数器保持在数组中，但我怎样才能在 O(n) 时间内按顺序打印它们？

Answer 1

你可以用数组和链表的链表来解决。

该数组是从计数器 ID 到我稍后将描述的计数器对象的映射。

主列表是一个列表，每个节点代表计数器数量。每个这样的节点都有一个包含该数量的所有计数器对象的列表，每个对象都有一个指向主列表节点(代表数量的节点)的指针。

当你增加计数器 i 时，你可以在 O(1) 时间内用你的数组获取你的对象，而不是你可以使用你必须到达的指针这个对象所在的节点，看看它代表的数量是多少。现在您可以简单地分离计数器对象，并在 O(1) 时间内将其附加到下一个列表(如果不存在则创建这样的列表)。

打印很简单，只需遍历主列表即可花费 O(n)。