algorithm - 有限空间平均计算

Question

假设我有 N 个整数，其中 N 可以变得很大，但每个整数都保证在 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++ 中，/ 运算符是除法运算符，而 % 实际上是余数运算符(实际上不是模运算符)。