2

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

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

有谁知道可以计算同一位空间中正整数列表的平均值的算法（最好是 O(N)）？没有做一些便宜的事情，比如使用两个整数来模拟一个更大的整数。

4

2 回答 2

5

假设您最初知道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++ 中，/运算符是除法运算符，%实际上是余数运算符（不是真正的模运算符）。

于 2013-04-19T23:25:45.387 回答
1

您可以计算运行平均值。如果您有元素的平均值A，N并且添加另一个元素E，则新平均值为(A*N+E)/(N+1)。根据除法比加法的分配性质，这等价于(A*N)/(N+1) + E/(N+1)。但是如果A*N溢出，你可以使用乘除法的结合性质，你可以将第一项转换为A*(N/N+1).

所以算法是：

n = 0
avg = 0
for each i in list
  avg = avg*(n/(n+1)) + i/(n+1)
  n = n+1
于 2013-04-19T23:32:38.180 回答