高效地查找未排序列表前缀的顺序统计量？

Question

A是一个整数数组，包含从1到n的整数，顺序随机。

我需要以至少对数时间访问第一个j个元素中第i大的元素。

到目前为止，我想到的是一个n x n矩阵M，其中(i, j)位置上的元素是前j个元素中第i大的元素。这样可以在常数时间内进行随机访问，但需要n^2的存储空间。

按构造方式，M按行和列排序。此外，每个列与相邻的列仅相差一个值。

有人能建议一种将M压缩到n log(n)空间或更小，并具有log(n)或更好的随机访问时间的方法吗？

- Dave

---

可以给一个输入和输出示例吗？ - stinepike

这是一个非常有趣的问题，我正在思考 :) - Patashu

Answer 1

我相信你可以在 O(log(N)) 的时间内访问元素，前提是进行了 O(N log(N)) 的预处理，并使用了额外的 O(N log(N)) 空间。以下是具体实现方法：

你可以扩展红黑树来支持 select(i) 操作，该操作以 O(log(N)) 的时间检索排名为 i 的元素。例如，可以参考此 PDF 或《算法导论》中的相关章节。

你可以以函数式的方式实现红黑树（即使是支持 select(i) 的增强版本），这样插入操作就会返回一个新树，该树与旧树除了 O(log(N)) 个节点之外完全相同。例如，可以参考 Chris Okasaki 的《纯函数数据结构》。

我们将构建一个数组 T，其中存储了纯函数增强红黑树，树 T[j] 存储了按从大到小排序的前 j 个元素的索引 0 ... j-1。

基本情况：在 T[0] 创建一个仅有一个节点的增强红黑树，其数据为数字 0，即数组 A 的前 1 个元素中第 0 大元素的索引。

归纳步骤：对于每个从 1 到 N-1 的 j，在 T[j] 中通过纯函数插入一个新节点，该节点的索引为 j，插入到树 T[j-1] 中。这最多会创建 O(log(j)) 个新节点；其余节点与 T[j-1] 共享。这需要 O(log(j)) 的时间。

构建数组 T 的总时间为 O(N log(N))，使用的总空间也为 O(N log(N))。

一旦创建了 T[j-1]，你可以通过执行 T[j-1].select(i) 访问数组 A 前 j 个元素中第 i 大的元素。这需要 O(log(j)) 的时间。请注意，可以在第一次需要时惰性地创建 T[j-1]。如果 A 很大且 j 始终相对较小，则可以节省大量时间和空间。

- rob mayoff

---

我刚想到这个解决方案，本来要在这里发布的，但你比我更快了。非常好的答案！ - templatetypedef

Answer 2

除非我误解了，您只是在查找另一个数组的前缀中的k-th order statistic。这可以使用一种算法来完成，我认为它被称为“快速选择”或类似的东西。基本上，它就像快速排序：

1. 选择一个随机枢轴
2. 交换数组元素，使所有较小的元素在一侧
3. 你知道这是第p+1大的元素，其中p是较小的数组元素的数量
4. 如果p+1=k，那么它就是解决方案！如果p+1>k，则在“较小”的子数组上重复。如果p+1

这里有一个（更好的）描述here，在Quickselect和Quicker Select标题下，以及在互联网上搜索k-th order quicksort solutions时通常都能找到。

虽然这种算法的最坏时间复杂度像快速排序一样是O(n2)，但如果您正确选择随机枢轴，其期望情况要好得多（也像快速排序）。我认为空间复杂度只会是O(n)；您只需制作一个前缀的副本来扰乱顺序即可。

- chm

---

看起来你需要为每个单独的 j 单独分配 O(j) 的空间，总共是二次空间。如果你能找到一种将它们合并的方法，那么你就有了一些东西。 - phs

嗯，备用数组的设置和拆卸将是O(n)，因此可以包含在时间复杂度中，并且您永远不需要同时使用超过O(j)的内存复杂度。 - chm