给定 x 类型的部分排序数组<y => x 的第一次出现出现在 y 的第一个之前，平均排序 O(n)

Question

i 被赋予一个任务来寻找一个采用数组 A 的算法，使得对于每个 x

示例数组可以是 1,2,1,30,1,1,2,1,40,30,1,40,2, 50, 40, 50, 30 输出应为 1, 1, 1, 1, 1, 1, 2, 2, 2, 30, 30, 30, 40, 40, 40, 50, 50

我应该表明建议的算法平均运行时间为 O(n)。

我不知道从哪里开始.. 我唯一知道的是如何从理论上分析循环或嵌套循环的平均情况 对于非常具体的情况

任何帮助将不胜感激。

Answer 1

在输入数组的一次迭代中，您可以：

• 按照首次出现的顺序收集唯一值

• 数一下你每人有多少个

利用这些信息，您可以生成排序的输出。