python - 查找列表中添加分数排名平均值的有效方法。可能是更有效的排序方式或数学方式？

Question

我正在尝试解决一个问题，我需要找到添加到列表中的一堆分数的排名平均值。

例如，如果输入是:5个10020015017050

那么程序应该输出2.2

还有5个分数要加

当输入 100 时，它排名第 1

当输入 200 时，它排在第 1 位

当输入 150 时，它排名第 2

当输入170时排名第2

当输入 50 时，它排名第 5

然后 (1 + 1 + 2 + 2 + 5) = 2.2

现在我有一个完美的解决方案，但它对于大型测试用例来说不够快。

games = input()
lst = []
acc = 0.0
counter = 0.0
for i in range(0, games):
    number = input()
    lst.append(number)
    lstt = sorted(lst)
    lsttt = lstt[::-1]
    acc += (lsttt.index(number) + 1)
print acc / games

现在我正在使用默认的 python 排序函数，我认为使用不同类型的排序可以使它更快。这是问题所在还是有更好的数学方法？

Answer 1

您可以使用 bisect模块在 O(log(n)) 时间内找到插入点:

import bisect

games = input()
lst = []
acc = 0.0
counter = 0.0
for i in range(games):
    number = input()
    pos = bisect.bisect(lst, number)
    lst.insert(pos, number)  # O(log(n)) for the search, but O(n) for the insertion
    acc += len(lst) - pos
print acc / games

这是对您的算法的改进，因为它是 O(n^2) 而不是 O((n^2)*log(n))。如果仍然太慢，您可能需要考虑使用树。