arrays - 具有特定值的数组

Question

给定一个大小为 n 的数组，其中:数组的 1/2 具有单个(未知)值。数组的 1/4 具有单个(未知)不同值。依此类推 1/8、1/16、1/32给出一个算法对数组进行排序。您不能使用查找中值算法

所以我想的是:只有 logn 个不同的值有一个在 O ( n*loglogn) 上使用二叉堆的简单解决方案看起来是个需要O(n)解决的问题

Answer 1

这是一种可能的方法:

• 扫描数组并在 amortized 的哈希表中存储元素频率(有 log n 个不同的元素)准时;这是可行的，因为 we can do insertions in amortized O(1) time ;
• 现在对这些 log n 元素运行经典排序算法:这在确定性的 O(log n log log n) 时间内是可行的，例如使用堆排序或合并排序；
• 现在扩展排序数组---或者创建一个新数组并使用排序数组和哈希表填充它---使用哈希表中的频率；这在 O(n) 摊销时间内是可行的。

因此，整个算法在分摊的 O(n) 时间内运行，即，它主要通过消除重复项和扩展排序数组来实现。空间复杂度为O(n)。

这基本上是最优的，因为您需要“接触”所有元素以打印排序数组，这意味着我们在运行时有一个匹配的 Omega(n) 下界。