根据特定条件在 O(n) 内排序算法

Question

给定一个包含 n−1 个数字的数组 A，其中 n = 2k 对于某个整数 k。其中一个值恰好出现 n/2 另一个恰好出现 n/4，依此类推。更正式地说，对于所有 1 ≤ k ≤ log n ，存在一个在数组中恰好出现 n/2^k 次的值。描述一个运行时间复杂度为 θ(n) 的对 A 进行排序的算法，并分析其运行时间。 示例：输入：5,1,2,1,2,2,2 输出：1,1,2,2,2,2,5

一些重要提示： 1.时间复杂度应该是最坏情况 2.不允许使用字典 3.解决方案应该使用堆栈或其他基本数据结构

我尝试使用计数排序，但它不起作用，因为数组不包含从 0 开始的值。 我还考虑过使用哈希映射，但时间复杂度是预期的，而不是最坏的情况。 感谢您提前的帮助

Answer 1

我怀疑有一种更好的方法可以利用“n/2，n/4，...等”属性，但是在将输入修改为完全非负之后是否可以使用计数排序？

例如：迭代输入，找到小于零的最小数字

x

，然后进行第二次迭代，同时构造一个修改后的列表，将

x

添加到所有值。然后，您可以对这个仅包含非负数的修改列表使用计数排序。由于问题表明输入仅是数字，而不是其他类型的可排序事物（例如字母），因此这应该是可行的。

当然，这会通过在 n-1 个项目上添加至少两次迭代来影响运行时间（如果您通过迭代计数排序输出并减去

x

来单独构造最终结果，而不是在计数中这样做，则为 3 次）排序），但它应该保持在 O(n + k) 的范围内，其中 k 是初始输入中的最大值加上

x

。您确实牺牲了至少

k

空间，这可能相当大，但所述问题不会施加空间限制。