6

我需要设计一个数据结构,它可以有效地支持对存储的(我认为合适的)数字序列进行以下操作:

  • 将整数添加到序列x的第一个元素i
  • k在序列末尾追加一个整数
  • 删除序列的最后一个元素
  • 检索序列中所有元素的平均值

例子

从空序列开始[]

  • 追加 0 ( [0])
  • 附加 5 ( [0, 5])
  • 附加 6 ( [0, 5, 6])
  • 将 3 添加到序列中的前 2 个元素 ( [3, 8, 6])
  • 检索平均值 5.66 ( [3, 8, 6])
  • 删除最后一个元素 ( [3, 8])
  • 检索平均值 5.5 ( [3, 8])

之前的工作

我考虑过使用Fenwick 树Topcoder 社论),但为此我需要为 Fenwick 树的初始化指定序列的最大大小,这不一定知道。但是,如果我有序列可以支持的最大元素数量,O(lg N)那么如果我还保存序列中所有元素的总和,我就可以支持这些操作。

编辑:问题是针对Codeforces 问题,我需要所有操作的亚线性运行时间,因为在最坏的情况下,添加到第一个元素可能与添加到整个序列相同

4

6 回答 6

6

您是否考虑过使用链表加上当前长度和总和?对于每个操作,您可以通过不断的额外工作来保持当前平均值(您知道列表的长度和总和,并且所有操作都以恒定的方式更改这两个值)。

唯一的非常量操作是将常量添加到任意前缀,这将花费与前缀大小成正比的时间,因为您需要调整每个数字。

要使所有操作保持不变(摊销)不变需要更多的工作。不使用双向链表,而是使用堆栈返回数组。数组中的每个槽i现在都包含 at 的数字i和要添加到每个元素的常量,直到i. (请注意,如果您说“将 3 添加到元素 11 之前的每个元素”,则插槽 11 将包含数字 3,但插槽 0-10 将为空。)现在每个操作都与以前一样,除了附加一个新元素涉及标准的数组加倍技巧,当您从队列末尾弹出最后一个元素时,您需要(a)在该插槽中添加常量,以及(b)将插槽中的常量值添加到插槽i的常量i-1. 所以对于你的例子:

附加0: [(0,0)], sum 0, length 1

附录 5: ([(0,0),(5,0)], sum 5, length 2

附录 6: [(0,0),(5,0),(6,0)], sum 11, length 3

将 3 添加到序列中的前 2 个元素:[(0,0),(5,3),(6,0)], sum 17, length 3

检索平均值 5.66

删除最后一个元素[(0,0),(5,3)], sum 11, length 2

检索平均值 5.5

删除最后一个元素[(0,3)], sum 3, length 1

这里有一些 Java 代码可能更清楚地说明了这个想法:

class Averager {
  private int sum;
  private ArrayList<Integer> elements = new ArrayList<Integer>();
  private ArrayList<Integer> addedConstants = new ArrayList<Integer>();

  public void addElement(int i) {
    elements.add(i);
    addedConstants.add(0);
    sum += i;
  }

  public void addToPrefix(int k, int upto) {
    addedConstants.set(upto, addedConstants.get(upto) + k);
    sum += k * (upto + 1);
    // Note: assumes prefix exists; in real code handle an error
  }

  public int pop() {
    int lastIndex = addedConstants.length() - 1;

    int constantToAdd = addedConstants.get(lastIndex);
    int valueToReturn = elements.get(lastIndex);
    addedConstants.set(
      lastIndex-1,
      addedConstants.get(lastIndex-1) + constantToAdd);
    sum -= valueToReturn;
    elements.remove(lastIndex);
    addedConstants.remove(lastIndex);
    return valueToReturn + constantToAdd;
    // Again you need to handle errors here as well, particularly where the stack
    // is already empty or has exactly one element
  }

  public double average() {
    return ((double) sum) / elements.length();
  }
}
于 2013-03-19T21:14:29.280 回答
2

听起来像一个双向链表,维护了一个头尾引用,以及当前的总和和计数。

将整数 x 添加到序列的前 i 个元素

从 *head 开始,添加x,下一项。重复i次数。sum += i*x

将整数 k 附加到序列的末尾

从 *tail 开始,使用 head = tail,tail = null 创建新项目。相应地更新 *tail、sum 和 count。

删除序列的最后一个元素

将 *tail 更新为 *tail->prev。更新总和,递减计数

检索平均值 5.5 ([3, 8])

返回总和/计数

于 2013-03-19T21:17:40.063 回答
1

为了满足第一个要求,您可以维护一个单独的添加操作数据结构。基本上,它是范围和增量的有序集合。您还可以维护这些添加的总和。因此,如果您在前三项中添加 5,然后在前 10 项中添加 12,您将拥有:

{3, 5}
{10, 12}

这些加法的总和是(3*5) + (10*12)= 135。

当被问及总和时,您提供项目的总和加上这些加法的总和。

您唯一遇到的麻烦是当您删除列表中的最后一项时。然后,您必须浏览此添加内容集合以找到包含最后一项(您要删除的项)的任何内容。该数据结构可以是哈希映射,键是索引。因此,在上面的示例中,您的哈希映射将是:

key: 3  value: 5
key: 10 value: 12

每当您执行第一个操作时,您都会检查哈希映射以查看是否已经存在具有该键的项目。如果是这样,您只需更新那里的值而不是添加新的增量。并相应地更新总和。

有趣的。您甚至不必保留额外的总和。您可以在使用时更新总金额。

当您从列表中删除最后一项时,您会检查哈希映射以查找具有该键的项。如果有,则删除该项目,减少键,然后将其添加回哈希映射(或使用该键更新现有项目,如果有的话)。

所以,使用 mattedgod 提出的双向链表,总和就是他提出的。然后使用此哈希映射来维护列表中添加的集合,并相应地更新总和。

于 2013-03-19T22:18:06.957 回答
1

我建议您尝试使用Binary Indexed Tree

它们允许您访问 O(Log(n)) 中的累积频率。

您还可以按 log(i) 顺序添加到前 i 个元素。

但是,不要将前 i 个元素增加 X,而只需将第 n 个元素增加 X。

要删除最后一个元素,也许有另一棵树,它加起来累计删除了多少。(因此,不是删除,而是将该数量添加到另一棵树中,在访问第一棵树时总是从结果中减去)。

对于追加,我建议你从一棵大小为 2*N 的树开始,它会给你空间。然后如果你得到大于 2*N 的大小,添加另一个大小为 2*N 的树。(不完全确定最好的方法,但希望你能弄清楚)。

于 2013-03-19T21:45:10.047 回答
1

这个数据结构可以只是一个元组 (N, S),其中 N 是计数,S 是总和和一堆数字。没有什么花哨。除了第一个是 O(i) 之外,所有操作都是 O(1)。

于 2013-03-19T21:16:52.833 回答
0

第 174 轮问题制定者发表了本轮的社论。你可以在这里找到它。您还可以查看一些公认的解决方案:PythonC++

于 2013-03-19T21:45:03.253 回答