13

A1是从到n随机顺序的整数数组。

我需要至少在日志时间内随机访问i第一个元素的第 th 大元素。j

到目前为止，我想出的是一个n x n矩阵，其中位置M中的元素是第一个中最大的。这给了我恒定时间的随机访问，但需要存储。(i, j)ijn^2

按构造，M按行和列排序。此外，每一列与其相邻列的差异只有一个值。

任何人都可以建议一种方法来压缩M到n log(n)空间或更好，具有log(n)或更好的随机访问时间？

4

2 回答 2

10

我相信你可以在 O(log(N)) 时间内执行访问，给定 O(N log(N)) 预处理时间和 O(N log(N)) 额外空间。就是这样。

您可以扩充红黑树以支持在 O(log(N)) 时间内select(i)检索排名中的元素的操作。i例如，请参阅此 PDF或算法简介的相应章节。

您可以以一种功能性的方式实现一棵红黑树（甚至是扩展为 supportselect(i)的），这样插入操作会返回一棵新树，该树与旧树共享除 O(log(N)) 之外的所有节点。例如，参见Chris Okasaki 的Purely Functional Data Structures。

T我们将构建一个纯功能增强的红黑树数组，以便树T[j]存储从大到小排序0 ... j-1的第一个j元素的索引。A

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

归纳步骤：对于j从 1 到的每一个N-1，在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]创建后，您可以通过执行访问第一个元素i中的第 th 大元素。这需要 O(log(j)) 时间。请注意，您可以在第一次需要时延迟创建。如果很大，总是比较小，这样会节省很多时间和空间。jAT[j-1].select(i)T[j-1]Aj

于 2013-03-12T05:52:06.623 回答
3

除非我误解，否则您只是在找到一个数组的k 阶统计量，它是另一个数组的前缀。

这可以使用我认为称为“快速选择”的算法或类似的算法来完成。基本上，它就像快速排序：

  1. 采取随机枢轴
  2. 交换数组元素，使所有较小的元素都在一侧
  3. 您知道这是第 p+1 个最大元素，其中 p 是较小数组元素的数量
  4. 如果 p+1 = k，这就是解决方案！如果 p+1 > k，在“较小的”子数组上重复。如果 p+1 < k，在更大的“子数组”上重复。

在 Quickselect 和 Quicker Select 标题下有一个（很多）更好的描述，如果您搜索 k 阶快速排序解决方案，通常也只是在 Internet 上。

尽管该算法的最坏情况时间是 O(n2)，如快速排序，但如果您正确选择随机枢轴，其预期情况会好得多（也类似于快速排序）。我认为空间复杂度只是 O(n); 你可以只复制一份你的前缀来弄乱订购。

于 2013-03-12T05:50:18.597 回答