开发者社区> 问答> 正文

我的代码的哪一部分导致了“超时错误”,为什么?

我尝试在Hackerrank上解决这个问题:https://www.hackerrank.com/挑战者/攀上排行榜。问题陈述基本上是说,有两组分数一个是玩家,另一个是Alice我们必须使用密集排序来显示Alice的等级当与其他玩家的分数相比较时。它在大型测试用例上给我超时错误。我已经使用了论坛上关于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

问题来源StackOverflow 地址:/questions/59386725/which-part-of-my-code-is-causing-a-time-out-error-and-why

展开
收起
kun坤 2019-12-25 21:53:02 438 0
1 条回答
写回答
取消 提交回答
  • 您的代码中有几个问题,但最重要的问题如下。

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

    在每次迭代中,您将Alice的分数添加到分数中,然后对分数进行排序。这里的代价已经是O(nlog(n)),其中n -元素在分数中的数量。因此,总时间复杂度变为O(nnlog(n))。这太多了,因为n可以达到200000,所以对于您的解决方案,它可以达到200000200000log(200000)操作。 当然,还有一个问题:

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

    但是由于循环时间复杂度是O(n),所以它仍然没有前一个那么糟糕。 存在一个O(nlog(n)))时间复杂度的解。我将给出一个总体的想法,这样您就可以轻松地自己实现它。 因此,所提出的解决方案的总时间复杂度为O(nlog(n))。它将通过所有的测试用例(我已经尝试过了)。

    2019-12-25 21:53:14
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
面向失败设计 立即下载
fibjs 模块重构从回调到协程--陈垒 立即下载
fibjs 模块重构从回调到协程 立即下载