我尝试在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
您的代码中有几个问题,但最重要的问题如下。
...
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))。它将通过所有的测试用例(我已经尝试过了)。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。