给定N个任意整数，如何找到这些数字的上半部分的平均值？是否有O(n)解决方案？如果不是，有可能证明那是不可能的吗？
最佳答案
首先，找到给定数组的median(它为takes linear time)。
然后，只需遍历数组并对所有大于中位数的元素求和。
计算您求和的元素数(M)。如果为M < N/2，则意味着等于中位数的几个元素(即N/2 - M)属于上半部分。将您的总和加上许多中值。我们需要这种复杂性，因为我们不知道上半部分有多少个中值元素(可以有几个):如果全部考虑，我们最终可能会累加超过N/2元素。
现在，您有了数组上半部分的总和。除以N/2，您就完成了。