algorithm - 使用附加数据结构的线性排序(查找集合中值的时间复杂度为 O(1)，添加元素的时间复杂度为 O(1))

Question

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

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

Answer 1

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

1. 扫描数组以查找最小和最大元素。将此称为min 和max。
2. 以任意顺序将所有数组元素插入到数据结构中。
3. 插入 n - 1 个 min - 1 副本。中位数现在是原始数组中的最小元素。
4. 重复 n - 1 次:
   • 插入 max + 1 的两个副本。
   • 读取中位数，它现在将成为原始数组中按升序排列的下一个元素。

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

1. 求最小值和最大值的时间复杂度为 O(n)，
2. 插入n个元素是n * O(1) = O(n)，
3. 插入 n-1 个元素的时间为 (n - 1) * O(1) = O(n)，
4. 插入两个元素并读取中位数的时间复杂度为 O(1)，因此执行 n - 1 次的时间复杂度为 O(n)。