我正在尝试在 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
最佳答案
您的代码中存在一些问题,但最重要的一个是以下问题。
...
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))
。它将通过所有测试用例(我已经尝试过了)。
关于python - 我的代码的哪一部分导致了 "Time-Out Error",为什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59386725/