See*_*ker 5 algorithm
给定N个任意整数,如何找到这些数字的上半部分的平均值？有O(n)解决方案吗？如果没有,是否有可能证明这是不可能的？
P S*_*ved 13
首先,找到给定数组的中位数(需要线性时间).
然后,只需遍历数组并总结所有大于中位数的元素.
计算你总结的元素数量(M).如果M < N/2,那么这意味着几个等于中值的元素(即,N/2 - M)属于上半部分.添加许多中值的总和.我们需要这种复杂性,因为我们不知道有多少中间元素(可能有几个)属于上半部分:如果我们全部采用它们,我们最终可能总结了多个N/2元素.
M
M < N/2
N/2 - M
N/2
现在你有了数组上半部分的总和.除以N/2,你完成了.
归档时间：
15 年，2 月 前
查看次数：
1608 次
最近记录：