如何在没有任何库或模块的情况下优化包含计数的代码？

Question

这是我参加的法语编码竞赛（Algoréa）准备活动的一部分。再一次，这不是真的，只是热身运动

程序应该接收一组作为整数的位置，并且需要输出一个位置经过的最大时间。例如，1 3 2 6 2意味着从1开始，然后到3，经过中间的所有位置，然后返回到2，然后是6，依此类推。这里的输出是4，因为第二个位置已经通过了4次

def move(x1, x2, l):
    if x1 < x2:
        l.extend(range(x1, x2))
    else:
        l.extend(range(x2, x1))


positions = []
for i in range(int(input())):
    positions.append(int(input()))

p = [] # positions, but instead of finding [1, 3] you would find [1, 2, 3]
for i in range(len(m) - 1):
    move(m[i], m[i + 1], p)

result = [] # count how many times each space was passed
for i in range(max(m)):
    wall.append(result.count(i))

print(max(result))

这很容易，但要获得最大的积分，您需要尽可能优化程序。。。这就是我被困的地方。我最初只是让它在每次传递时增加列表中相应的索引，但切换到在最后计算每个值，正如您在这里看到的，我认为这可能会更快，但事实并非如此。我在任何地方都找不到这个问题的答案（上面提到的准备练习是2018年真实比赛的练习，所以我想我可能能找到一些答案）

我不能使用任何库或模块，甚至不能使用内置的库或模块，所以我只能使用list.count()

这里有什么可以做得更好的地方吗？我知道这个问题可能很难回答

Answer 1

正如评论所说，我不确定你在试图优化什么。然而，您的方法使用（潜在的）二次空间，而线性空间就足够了。您需要保留一个计数数组，并且每次移动，而不是追加范围，只是将范围覆盖的索引增加1。然后进行最后一次扫描以找到argmax

Answer 2

在这里，生成每个步骤的列表并将它们连接在一起。构建一个字典，其中包含从最小位置到最大位置的键值对及其计数。最后，找到最大计数及其位置

a = [1, 3, 2, 6, 2]

items = []
for i in range(len(a)-1):
    items += list(range(*sorted(a[i:i+2])))
result = {i:items.count(i) for i in range(min(items), max(items)+1)}

print(max(result.items(), key=lambda item:item[1]))