我需要设计一个数据结构来有效地支持对存储的(我认为合适的)数字序列进行以下操作:
- 将整数
x
添加到序列的第一个i
元素 - 在序列末尾追加一个整数
k
- 删除序列的最后一个元素
- 获取序列中所有元素的平均值
例子
以空序列开始 []
- 追加 0 (
[0]
) - 追加 5 (
[0, 5]
) - 追加 6 (
[0, 5, 6]
) - 向序列中的前 2 个元素添加 3 (
[3, 8, 6]
) - 检索平均值 5.66 (
[3, 8, 6]
) - 删除最后一个元素 (
[3, 8]
) - 检索平均值 5.5 (
[3, 8]
)
以前的工作
我考虑过使用 Fenwick Trees ( Topcoder Editorial ) 但为此,我需要为 Fenwick 树的初始化指定序列的最大大小,这不一定是已知的。但是,如果我有序列可以支持的最大元素数,我可以支持对 O(lg N)
的这些操作,前提是我还保存序列中所有元素的总和。
编辑:问题是针对 Codeforces problem 的我需要所有操作的次线性运行时间,因为在最坏的情况下,添加到第一个元素可能与添加到整个序列相同
最佳答案
有没有考虑过用链表加上当前的长度和和?对于每个操作,您可以通过不断的额外工作来维持当前平均值(您知道列表的长度和总和,并且所有操作都会以恒定的方式更改这两个值)。
唯一的非常量操作是向任意前缀添加一个常量,这将花费与前缀大小成比例的时间,因为您需要调整每个数字。
要使所有操作恒定(摊销)恒定需要更多的工作。不使用双向链表,而是用堆栈支持数组。数组中的每个槽 i
现在都包含 i
处的数字和要添加到 i
之前的每个元素的常量。 (请注意,如果您说“将 3 加到元素 11 之前的每个元素”,槽 11 将包含数字 3,但槽 0-10 将为空。)现在每个操作都和以前一样,除了附加一个新元素涉及标准数组加倍技巧,当您从队列末尾弹出最后一个元素时,您需要 (a) 在该槽中添加常量,以及 (b) 从槽 i< 添加常量值
到插槽 i-1
的常量。所以对于你的例子:
附加 0:[(0,0)],总和 0,长度 1
附加 5:([(0,0),(5,0)],总和 5,长度 2
附加 6:[(0,0),(5,0),(6,0)],总和 11,长度 3
将序列中的前 2 个元素加 3:[(0,0),(5,3),(6,0)],总和 17,长度 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();
}
}
关于algorithm - 序列平均值的高效数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15510486/