c++ - 以 O(1) 表示法查找数字列表的平均值 - 常数时间

Question

事情是这样的，我的任务是创建一个包含一些数字的数组，之后该数组可以在任何位置接受任何其他相同类型的数字。当我得到最终的数组（带有添加的数字）时，我需要以恒定的 O(1) 时间找到内部数字的平均值。我怎么做？！这是我的例子

元素：5 12 7 9 31 平均：12.8

Answer 1

如果这是一个数组类，您可以在添加和更新所有数字时跟踪它们的总和。然后当所有更新完成时，只需将总和除以元素数即可得到平均值，并且由于总和是预先计算的，因此平均值的计算将是 O(1)。

如果这是一个简单传递的原始内存数组，那么计算平均值将需要对所有数字求和，这是一个 O(N)，除非有人正在玩关于操作是什么的语义游戏。