algorithm - 大小为 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)第 number 和 (n - 3*log(n))在 O(n) 中快速选择的第 th 个数字.

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

我们现在有n - (n - 2*log(n)) = 2*log(n)范围为 2^n 的项目.

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