algorithm - 使用附加数据结构进行线性排序(O(1) 找到集合的中位数，O(1) 用于添加元素)

Question

假设我们在数组和魔法 DS 中有任意元素(我们可以在 O(1) 中比较它们)，我们可以在 O(1) 中添加元素并在 O(1) 中找到 DS 中元素的中位数。我们无法从 DS 中删除元素，并且数组中没有相等的元素。此外，我们可以根据需要创建任意数量的 DS。

问题:有没有办法使用这个 DS 对 O(n) 中的数组进行排序？

Answer 1

是的，如果这个数据结构存在，那么它可以用来在 O(n) 时间内排序。

扫描数组以找到最小和最大元素。调用 min和 max .

以任意顺序将所有数组元素插入数据结构。

插入 n - 1 份 min - 1 .中位数现在是原始数组中的最小元素。

重复 n - 1 次:

插入两份max + 1 .

读取中位数，该中位数现在将是原始数组中升序的下一个元素。

这个过程需要 O(n) 时间，因为

找到最小值和最大值是 O(n)，

插入 n 个元素是 n * O(1) = O(n),

插入 n-1 个元素是 (n - 1) * O(1) = O(n),

插入两个元素并读取中位数是 O(1)，所以这样做 n - 1 次是 O(n)。