时间戳

首页 > 解决方案 > 如何优化我的代码以解决 Hackerrank 问题“攀登排行榜”？

python - 如何优化我的代码以解决 Hackerrank 问题“攀登排行榜”？

问题描述

问题的链接：https ://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

对于我的解决方案，它通过了两个“运行代码”测试用例，但在提交时，它只通过了 12 个测试用例中的 8 个，但由于超时而失败了 4 个。我猜解决方案本身是正确的。请对如何优化解决方案有任何想法？

一些小测试用例：

# Small Test case 1
ranked = [100, 90, 90, 80] ## already in descending order
player = [70, 80, 105]
## expected ans = [4, 3, 1]

# Small Test case 2
ranked = [100, 90, 90, 80] ## already in descending order
player = [70, 90, 105]
## expected ans = [4, 2, 1]

# Small Test case 3
ranked = [100, 100, 50, 40, 40, 20, 10] ## already in descending order
player = [5, 25, 50, 120]
## expected ans = [6, 4, 2, 1]

我的解决方案：

def climbingLeaderboard(_r, _p):
    #print(f"Params passed:\nranked={_r}\nplayer={_p}")
    ans = list()
    for pidx, pscore in enumerate(_p):
        #print(f"\nPos {pidx} : Player score = {pscore}")
        crank = 1 ## set current rank as 1 at start of evaluation of a player score
        if pscore >= _r[0]:
            ans.append(1)
            continue
        for ridx, rscore in enumerate(_r[1:]):
            #print(f"ridx={ridx} , RankedScore={rscore} , PlayerScore = {pscore} , crank={crank}")
            if rscore < _r[ridx]: ## current ranked score < previous ranked score
                crank += 1
            if pscore >= rscore:
                ans.append(crank)
                break
        else:
            ans.append(crank+1)
        #print(f"now ans={ans}")
    return ans

print(f"\n\nFinal answer = {f1(ranked, player)}")

标签： python

解决方案

最明显的时间损失是您使用的是线性搜索，对于现有玩家来说是O(n) 。n接下来是您在两次搜索之间放弃所有学习，因此您必须对您放置的分数进行m独立搜索。m

将线性搜索替换为_r（长度为n）的二分搜索。这将加快您的速度，从而有可能通过时序测试。但是，为了提高效率，请记住找到最后一个分数的位置，这样您就不会搜索_r您知道不能包含下一个分数的区域。例如，如果您发现第一个分数适合_r[idx1]，那么您的下一个二分搜索应该只覆盖_r[:indx1]（玩家分数按升序排列，因此您不必搜索排名板上的任何较低位置）。

你能从那里拿走吗？

为了提高速度，您可以对排行榜上的分数分布做出一些假设。在现实世界中，这是合理的，尤其是在排行榜非常大的情况下。如果您使用简单的插值搜索，您将在预期情况下节省更多时间。

推荐阅读