您是否考虑过使用链表加上当前长度和总和?对于每个操作,您可以通过不断的额外工作来保持当前平均值(您知道列表的长度和总和,并且所有操作都以恒定的方式更改这两个值)。
唯一的非常量操作是将常量添加到任意前缀,这将花费与前缀大小成正比的时间,因为您需要调整每个数字。
要使所有操作保持不变(摊销)不变需要更多的工作。不使用双向链表,而是使用堆栈返回数组。数组中的每个槽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();
}
}