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

Question

问题的链接：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)}")

Answer 1

最明显的时间损失是使用线性搜索，这是对n现有玩家的O（n）。下一步是在两次搜索之间扔掉所有的学习内容，因此你必须对你的m分数进行m独立搜索

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

你能从那里拿走吗

---

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