arrays - 求和未排序数组中元素的算法

Question

我有两个数组:

• 数组 A = [a₁, a₂, …, a_n] 未排序。
• 数组 B = [b₁, b₂, …, b_k] 已排序，并且元素比 A 少很多(即:k ≪ n).

对于每个 b_i，我想计算最大的 b_{数组A中的em>i}个元素，例如if

• A = [10, 5, 3, 9, 8, 15, 4, 7, 11, 1, 20, 6]
• B = [2, 3, 4, 6, 7]

然后我想要 A 中第 2、3、4、6 和 7 个最大元素的总和:

• [20+15, 20+15+11, 20+15+11+10, 20+15+11+10+9+8, 20+15+11+10+9+8+7]<
• 即:[35, 46, 56, 73, 80]

我知道如何在 O(n) 时间内计算 b_i 最大元素的总和，所以我可以很容易地为在 O(nk) 时间内运行的整个东西编写一个算法；但我需要一个在 O(n log k) 时间内运行的算法。

那么，我怎样才能在 O(n log k) 时间内完成此操作？

Answer 1

基本上，您想在第一个数组中找到 k 个最大的元素。

这是算法的草图。您遍历第一个数组。您将元素插入到一个数据结构中——比方说一个 b 树。插入到数据结构中的是 log(k)，因为数据结构的结构仅限于 k 个元素。因此，对于 k+1 记录，插入有点不同，因为较大的值会覆盖较小的值。 (有比 b 树更好的数据结构，例如堆，但您可能更熟悉树。)

无论如何，插入到这个数据结构中的是log(k)。您可以在 O(n * log(k)) 操作中创建它。然后，你只需要读取数据结构，即k。因为 k < n，它不会增加复杂性。因此，这就是您构建此类算法的方式。