algorithm - 如何计算高于 Int 列表平均值十分之一的值的百分比

Question

我有一长串整数，我想计算高于或高于均值十分之一的数字的百分比。也就是说，我想计算分数的百分位数 mean/10。这是一个天真的方法(在 Python 中，但这并不重要):

ls = [35,35,73,23,40,60,5,7,3,4,1,1,1,1,1]
length = 0
summ = 0
for i in ls:
    length += 1
    summ += i

mean = float(summ) / float(length)
print('The input value list is: {}'.format(ls))
print('The mean is: {}'.format(mean))
tenth_mean = mean / 10
print('One tenth of the mean is: {}'.format(tenth_mean))

summ = 0
for i in ls:
    if (i >= tenth_mean):
        summ += 1
result = float(summ) / float(length)
print('The percentage of values equal or above one tenth of the mean is: {}'.format(result))

输出:

The input value list is: [35, 35, 73, 23, 40, 60, 5, 7, 3, 4, 1, 1, 1, 1, 1]
The mean is: 19.3333333333
One tenth of the mean is: 1.93333333333
The percentage of values equal or above one tenth of the mean is: 0.666666666667

这种方法的问题是我必须遍历列表两次。有什么聪明的方法可以避免这种情况吗？

我看不到任何值，因为我首先需要计算平均值才能知道要在计数中保留哪些值(第二个循环)。

此外，我想针对多个百分比(即平均值的十分之一、平均值的五分之一等)执行此操作。这可以在第二个循环中轻松实现。我只是想指出这一点。

输入数组不服从任何分布。

编辑:可能值的范围只有几千。值的总数约为 30 亿。

编辑:修正了上面“percentile”这个词的用法。

Answer 1

如果列表中有很多查询，进行一些预处理以将时间复杂度降低到 O(log(n)) 可能会有所帮助。

如果您对列表进行排序并计算列表的平均值(使用 python 函数)，则可以使用二进制搜索在列表中找到百分位数。因此，查询时间为 O(log(n))。