python - 如何优化 o(n**2) 算法成为 o(nlogn) 或 o(n)？

Question

我正在尝试完成一个给你两个数组的hackerrank问题。一个是分数列表，另一个是来自特定人员的分数列表。您必须确定每个分数的那个人的排名。例如：

scores = [100,90,80]
alice = [80,90,100]

输出应该是 3,2,1，因为如果你要将它与数组 score 中的分数进行比较，这就是 alice 的放置方式。如果平局，那么您将获得相同的排名。

我曾尝试仅使用一个循环并使用 range 命令，但这完全失败了，而且我没有得到远程接近的答案。工作解决方案是 ao(n**2) 解决方案，它通过了所有测试，除了大的测试，其中它超时。

def climbingLeaderboard(scores, alice):
    scores = list(set(scores))
    new_list = []
    alcount = 1
    for i in alice:
        for x in scores:
            if i < x:
                alcount += 1
        new_list.append(alcount)
        alcount = 1
    return new_list

任何帮助将不胜感激！

标签： pythonoptimization

Answer 1

将分数放入字典中：

scores = {100:1, 90:2, 80:3}

现在是直接查找 Alice 的每个分数以转换为所需的输出列表。