1

我有以下问题：

给定一个整数数组 A，并给定 t个不重叠的部分 [L1,R1],[L2,R2]...[Lt,Rt]

使得每个部分都是数组 (A) 处的开始索引 (Li) 和结束索引 (Ri)，

找到一个数据结构，它以 O(t + klogk) 复杂度返回这些部分中的前 k 个元素（索引在部分中，元素在数组 A 中）。

非常感谢帮助者 Avihai。

4

2 回答 2

1

问题的措辞有点模棱两可：什么算作复杂性操作的一部分O(t+klogk)？

我在回答这个问题时看到了 3 个选项。对于前两个，我认为这是解释原始问题的错误方式，我提供了答案。对于第三个也是最后一个选项，我没有解决方案。我仍然认为有必要把问题弄清楚，并将我的答案添加到前两个中。此外，如果不是不可能的话，在评论中添加对此事的长时间讨论也会令人困惑。

以下是我看到的用于回答我开始的问题的选项：

选项 1 - 数据结构构建（使用部分）不包括在内

从原始问题的当前措辞听起来，该问题要求可以使用数组A和部分预先构建的数据结构，[L1,R1],[L2,R2],...,[Lt,Rt]并且考虑复杂性要求的唯一操作是对数据结构执行的操作以提取最高k值。

这没有多大意义，因为目前尚不清楚为什么t在这种情况下会变得复杂？从您在评论中链接到 Juan 的答案的这个答案中，您可以看到，通过仅使用相关元素预先构建一个堆，您可以获得从O(klogk)数据结构中获取k最高价值的元素（一旦存在）。

选项 2 - 包括所有操作

如果我们阅读它，就好像问题要求将数据结构构建为考虑复杂性要求的操作的一部分（我们只得到数组和索引列表[L1,R1,L2,R2,...,Lt,Rt]并且必须使用它），那么复杂性要求不是有可能实现。如果你想建立一个数据结构，你至少需要检查所有需要插入数据结构的元素，如果你不想建立一个数据结构并且你打算使用数组作为它那么你将不得不检查你需要找到最大值的所有元素。无论哪种方式，如果你得到数组中的元素数量在t=1哪里L1=1, R1=n，你将不得不遍历其中的所有元素nAA（您没有关于A“元素”顺序的假设）。这意味着您至少需要O(n)并且要求是O(t+klogk). 为了更清楚地说明这些是完全不相关的数量 - 您可以考虑 的情况k=1，这意味着只找到最高元素，而A可以是任意长度（比如说 10,000）。

选项 3 - 仅使用数组豁免构建数据结构

这让我想到了问题背后的原始含义：A事先从给定的数组构建一个数据结构（其构建将不包含在复杂性要求中），以便稍后为您提供部分的索引[L1,R1],[L2,R2],...[Lt,Rt]和一个整数k您之前构建的数据结构将允许您获取原始数组中k由新给定索引 () 定义的部分中的最高元素。不幸的是，我还没有想出解决这个问题的办法——或者证明不存在这样的解决方案，但至少现在这个问题是有道理的。L1,R1,L2,R2,...,Lt,RtAO(t+klogk)

我很想知道哪个选项是问题的初衷，如果我想出选项 3 的解决方案，我将相应地编辑这个答案。

于 2016-09-08T13:19:37.790 回答
0

我会构建一个间接表 T，它将 [0..t] 映射到由部分映射的索引。

然后我会使用这个间接表运行 heapify 算法。每次算法访问 A[i] 时，它都会被 A[T[i]] 替换。

间接表构建和 heapify 都是 O(t)。获取前 k 个元素将花费 O(t log n)。

编辑： 维基百科在其文章中解释了如何在 O(t) 中构建堆。

基本上它是一系列冒泡操作：

for i from floor(A.size()/2) to 0:
    bubble_down(A, i)

文章中有一个证明为什么这是 O(t)。

于 2013-02-21T18:24:24.460 回答