空间平均计算有限

Question

假设我有N个整数,其中N可以变大,但每个int保证在0和某个上限M之间,其中M很容易适合有符号的32位字段.

如果我想计算这些N个整数的平均值,我不能总是在同一个有符号的32位空间中对它们进行求和并将它们全部除以 - 如果N太大,分子就有溢出的风险.这个问题的一个解决方案是仅使用64位字段进行计算,以保持较大的N,但此解决方案不会扩展 - 如果M是一个大的64位整数,则会出现同样的问题.

有谁知道一个算法(最好是O(N))可以计算同一位空间中正整数列表的平均值？没有像使用两个整数来模拟更大的一样便宜.

Answer 1

假设你M最初知道,你可以保留两个变量,一个是到目前为止的答案除以M,另一个是余数.

例如,在C++中:

int ans = 0, remainder = 0;
for (int i=0;i<N;i++) {
  remainder += input[i]; // update remainder so far
  ans += remainder/N; // move what we can from remainder into ans
  remainder%=N; // calculate what's left of remainder
}

在循环结束时,找到答案ans,其余部分在remainder(如果您需要除截断之外的舍入方法).

此示例适用于最大输入数M + N适合32位int的情况.

请注意,这应该适用于正整数和负整数,因为在C++中,/运算符是除法运算符,%实际上是余数运算符(实际上不是模运算符).