寻找整数数组的平均值

Question

假设您有一个 int 数组（使用任何具有固定大小 int 的语言）。 您如何计算最接近它们平均值的 int？

编辑：明确一点，结果不必存在于数组中。 也就是说，对于输入数组 [3, 6, 7]，期望结果是 5。此外，我想我们需要指定一个特定的舍入方向，因此如果您距离两个数字同样接近，则向下舍入。

编辑：这不是作业。 我已经五年没有作业了。 而且这是我第一次在 stackoverflow 上，所以请友好一些！

编辑：显然的方法是将总和除以数量，但可能会溢出，因此我正在尝试思考一种安全处理溢出的方法，适用于大型数组和大型 int。 我认为正确处理溢出（而不作弊并使用不同类型）是这个问题中最难的部分。

- fish

---

通过增加不使用更大的数据类型的人为限制，你似乎只是在刁难别人。请解释一下你为什么不能这样做。 - paxdiablo

我猜这更多是一个理论问题。在这里，我们有一个简单的、无处不在的函数，我们在学校就学过，但似乎很难在不超出函数定义域的情况下安全地计算它。更实际的是，可能没有更大的类型。 - fish

总有一个更大的类型，即使你必须自己实现它。任何其他解决方案都存在精度丢失的风险，因为您正在添加不同尺度的数字。这可能是可以接受的，这取决于您想要什么。 - paxdiablo

这个问题的表述本应该更好：当我回答时，它似乎是关于四舍五入的，但实际上是关于避免溢出的。我很想编辑和重写它，但不确定是否合适... - David Z

Answer 1

这是一种快速、合理的溢出安全方法，并且可以在事先不知道元素数量的情况下工作。

// The length of someListOfNumbers doesn't need to be known in advance.
int mean(SomeType someListOfNumbers) {  
    double mean = 0, count = 0;
    foreach(element; someListOfNumbers) {
        count++;
        mean += (element - mean) / count;
    }
    if(count == 0) {
        throw new UserIsAnIdiotException(
                  "Problem exists between keyboard and chair.");
    }
    return cast(int) floor(mean);
}

- dsimcha

Answer 2

那就先计算平均值，然后四舍五入到整数？round(mean(thearray)) 大多数语言都有可以指定舍入方法的工具。

编辑：结果发现这个问题实际上是关于避免溢出，而不是关于舍入。让我明确一点，我同意评论中说的那些话，这在实践中不是需要担心的事情，因为它很少发生，当它发生时，你总是可以使用更大的数据类型来解决。

我看到其他几个人给出的答案基本上是将数组中的每个数字除以数组的计数，然后将它们相加。这也是一个不错的方法。但只是为了好玩，这里是一个替代方案（C风格的伪代码）：

int sum_offset = 0;
for (int i = 1; i < length(array); i++)
     sum_offset += array[i] - array[i-1];
// round by your method of choice
int mean_offset = round((float)sum_offset / length(array));
int mean = mean_offset + array[0];

或者用另一种方式实现相同的功能：

int min = INT_MAX, max = INT_MIN;
for (int i = 0; i < length(array); i++) {
     if (array[i] < min) min = array[i];
     if (array[i] > max) max = array[i];
}
int sum_offset = max - min;
// round by your method of choice
int mean_offset = round((float)sum_offset / length(array));
int mean = mean_offset + min;

当然，您需要确保sum_offset不会溢出，如果数组中最大元素和最小元素之间的差大于INT_MAX，则可能发生溢出。在这种情况下，请将最后四行替换为以下内容：

// round by your method of choice
int mean_offset = round((float)max / length(array) - (float)min / length(array));
int mean = mean_offset + min;

趣闻：这种方法（或类似的方法）也能很好地计算元素聚集在一起的数组的平均值。

- David

---

你会如何计算平均值？ - fish

@fish - 我不是David，但我个人会通过将所有数字相加，然后将结果除以它们的数量来计算平均值，即有多少个数字就除以多少。这通常是一种非常有效的计算平均值的方法。 - Daniel Daranas

Answer 3

通过将数字相加并除以它们的数量，四舍五入计算总和：

mean = (int)((sum + length/2) / length;

如果您担心溢出问题，可以采取以下措施： ```html 如果您担心溢出问题，可以这样做： ```

int mean = 0, remainder = 0
foreach n in number
   mean += n / length
   remainder += n % length
   if remainder > length
       mean += 1
       remainder -= length
if remainder > length/2
   mean += 1
print "mean is: " mean

请注意，这并不是非常快速的。

- FryGuy

---

这是一个不错的开端，但是对于较大的长度，那个 remainder += n%length 可能会溢出。例如，如果长度为 INT_MAX/2 + 2，并且数组中的前两个条目为 INT_MAX/2 + 1，则会发生溢出。 - fish

确实可能发生这种情况，但在哪种体系结构下你能够在内存中拥有那么大的数组呢 :)..此外，它不能很好地处理负数。 - FryGuy

Answer 4

保证不会溢出：

length ← length of list
average ← 0
for each result in the list do:
    average ← average + ( result / length )
end for

如果您使用整数，由于截断，这会导致准确性方面的重大问题（六个4的平均值为0）

- eplawless

---

不会溢出是因为你使用了浮点数，或者你得到了不准确的答案（大多数情况下）。 - strager

Answer 5

欢迎。fish，希望您在这里过得愉快。

以下伪代码展示了如何在总和适合整数类型的情况下进行操作，并且 round 四舍五入到最近的整数。

在您的样本中，数字相加总和为16，除以3得到5 1/3，四舍五入为5。

sum = 0
for i = 1 to array.size
    sum = sum + array[i]
sum = sum / array.size
sum = round (sum)

- Pax

Answer 6

这个伪代码可以找到平均值并解决溢出问题:

double avg = 0
int count = 0
for x in array:
    count += 1
    avg = avg * (count - 1) / count   // readjust old average
    avg += x / count                  // add in new number

之后，您可以应用您的四舍五入代码。如果您的语言没有简单的四舍五入方法，那么类似这样的代码将起作用（当超过0.5时向上取整）：

int temp = avg - int(avg)   // finds decimal portion
if temp <= 0.5
    avg = int(avg)          // round down
else
    avg = int(avg) + 1      // round up

- MahlerFive

Answer 7

ARM汇编。未测试。永远不会溢出。（我希望如此。）

可能可以稍微优化一下。（也许使用FP / LR？）= S 可能在这里使用THUMB效果更好。

.arm

; r0 = pointer to array of integers
; r1 = number of integers in array
; returns mean in r0
mean:
stmfd sp!, {r4,r5}
mov r5, r1

mov r2, 0          ; sum_lo
mov r3, 0          ; sum_hi

cmp r1, 0          ; Check for empty array
bz .end

.loop:
ldr r4, [r0], #4
add r2, r2, r4
adc r3, r3, #0     ; Handle overflow
sub r1, r1, #1     ; Next
bnz .loop

.end:
div r0, r2, r3, r5 ; Your own 64-bit/32-bit divide: r0 = (r3r2) / r5
bx lr

- strager

Answer 8

获取平均值的伪代码：

double mean = 0
int count = 0
foreach int number in numbers
    count++
    mean += number - mean / count

round(mean) // rounds up
floor(mean + 0.5) // rounds up
ceil(mean - 0.5) // rounds down

舍入通常涉及添加0.5，然后截断（向下取整），这就是为什么3.5四舍五入到4。如果您想让3.5向下舍入到3，请自己编写舍入代码，但要反过来：减去0.5，然后找到上限。

编辑：更新要求（无溢出）

- Nikhil Chelliah