大小为 2^n 的整数的线性时间排序

Question

问题

我需要设计一个算法，该算法将整数列表作为输入，并返回一个大于第一个log(n)且小于最后n - 3 log(n)一个2log(n)元素的排序列表（换句话说，我需要一个排序的元素列表）。数组的整数在 0 到 2^n 之间。它们必须按线性时间排序O(n)，其中 n 是整个列表中的元素数。我们只需要排序元素的子集这一事实可能与找到解决方案有关，但我还没有找到它的关系。

我的解决方案

我尝试了两种解决方案。

1. 使用计数排序，但这会产生指数 ( 2^n) 时间和空间复杂度
2. 使用基数排序，但这会产生二次时间复杂度。这是因为与 T(n) = O(d*(n + b)) = O(log_b(2^n)*(n + b)) = O(n * log_b(2) * (n + b)) = O(n^2)b 的值无关。

如您所见，我对接下来要尝试的内容有些迷茫。提前致谢！

Answer 1

归功于 SomeWittyUsername 更正原始问题要求。

“大于第一个 log(n) 且小于最后 n - 3 个 log(n) 元素。”

找到log(n)个号码和(n - 3*log(n))在quickselect日数O(n)。

过滤列表以删除log(n) + n - 3*log(n) = n - 2*log(n)项目。

我们现在有n - (n - 2*log(n)) = 2*log(n)range 的项目2^n。

O(log(n))通过比较排序对元素进行排序需要O(log(n) * log(log(n))) << O(n)时间。