如何优化o(n ** 2)算法成为o(nlogn)或o(n)?

我正在尝试完成一个hackerrank问题,给您两个数组.一个是分数列表,另一个是来自特定人的分数列表.您必须确定每个分数的那个人的排名.
例如:

scores = [100,90,80]
alice = [80,90,100]

输出应为3,2,1,因为如果您将其与数组分数中的分数进行比较,这就是alice的放置方式.如果平局,则排名相同.

我尝试只使用一个循环并使用range命令,但是那完全失败了,而且我没有得到远程接近的答案.工作解决方案是o(n ** 2)解决方案,它通过了除大型测试以外的所有测试,但该测试超时了.

def climbingLeaderboard(scores, alice):
    scores = list(set(scores))
    new_list = []
    alcount = 1
    for i in alice:
        for x in scores:
            if i < x:
                alcount += 1
        new_list.append(alcount)
        alcount = 1
    return new_list

任何帮助将不胜感激!

解决方法:

将分数放入字典中:

scores = {100:1, 90:2, 80:3}

现在,可以直接查找每个Alice的乐谱,以转换为所需的输出列表.

上一篇:放慢我的JavaScript!如何让我的代码在执行之前等待过渡完成?


下一篇:(Java)存储具有索引属性的大量对象