python - 我的代码的哪一部分导致了 "Time-Out Error"，为什么？

Question

我正在尝试在 Hackerrank 上解决这个问题:https://www.hackerrank.com/challenges/climbing-the-leaderboard 。问题陈述基本上指出有两组分数，一组是玩家的，另一组是爱丽丝的，我们必须使用 dense ranking并显示爱丽丝与其他玩家的分数相比的排名。它在大型测试用例上给我超时错误。我已经使用了 Hackerrank 上的论坛建议并取得了成功，但我特别想知道我的代码中的问题。这是我的代码:

class Dict(dict):

    def __init__(self):
        self=dict()

    def add(self,key,value):
        self[key]=value

def climbingLeaderboard(scores, alice):

    alice_rank=[]
    for i in range(len(alice)):
        scores.append(alice[i])
        a=list(set(scores))
        a.sort(reverse=True)
        obj=Dict()
        b=1
        for j in a:
            obj.add(j,b)
            b+=1
        if alice[i] in obj:
            alice_rank.append(obj[alice[i]])
    scores.remove(alice[i])        
    return alice_rank

Answer 1

您的代码中存在一些问题，但最重要的一个是以下问题。

...
scores.append(alice[i])
a=list(set(scores))
a.sort(reverse=True)
...

在每次迭代中，您将 Alice 的分数添加到 scores 中，然后对 scores 进行排序。这里的成本已经是 O(nlog(n))，其中 n - scores 中的元素数量。因此，您的总时间复杂度变为O(n*n*log(n))。这太多了，因为 n 可以达到 200000，因此对于您的解决方案来说，它可能高达 200000*200000*log(200000) 操作。

当然，还有一个问题:

...
for j in a:
    obj.add(j,b)
    b+=1
...

但它仍然没有前一个那么糟糕，因为循环时间复杂度为 O(n)。

存在一个O(n*log(n))时间复杂度的解决方案。我会给你一个总体思路，以便你可以轻松地自己实现。

• 如果您还记得分数重复的玩家在排行榜上的位置相同，那么您可以将您的 分数 转换为不重复的数组，如 list(set(scores)) 在循环之前。在这种情况下，第一个位置对应于最高分，第二个位置对应于第二高分，依此类推(初始数组按每个问题陈述的降序排序)。
• 根据上述步骤，对于 Alice 的每个 score，您可以在数组中找到玩家得分小于或等于 score 的位置。由于数组已排序，因此查找将花费 O(log(n)) 时间。例如，如果玩家的分数是 40, 30, 10，Alice 的分数是 35，那么找到的位置将为 2 (对于算法描述，我认为第一个索引从1开始)，因为30占据了这个位置，这个位置是Alice的实际位置排行榜等可以立即打印。
• 另一个提示 - 您可以使用 bisect用于在数组中执行二分搜索的模块。

因此，所提出的解决方案的总体时间复杂度为O(n*log(n))。它将通过所有测试用例(我已经尝试过了)。