python - 减少时间消耗

Question

我正在为 this problem 编写代码:

Given an array A having N elements. Find total number of pairs (i,j) such that j < i and Aj = Ai.

这是我的代码:

raw_input()

l = list(map(int, raw_input().split()))

count = 0

for a in range(len(l)):
    count = count + l[a+1:].count(l[a])

print(count)

但不幸的是，该代码花费了很多时间。您有什么建议可以帮助我减少时间消耗吗？我的意思是，如何减少 for 循环中消耗的时间。我觉得 list.count 方法需要很多时间，所以你有什么想法可以替换它。

Answer 1

您可以通过使用比 .count() 更快的方式检查成员资格来加快速度。例如，dict 查找速度非常快:

from collections import defaultdict

raw_input()

l = list(map(int, raw_input().split()))

keys = defaultdict(list)

for i, v in enumerate(l):
    keys[v].append(i)

for value, keys in keys.items():
    print("Value %d appears at indices %s." % (k, ", ".join(keys)))

然后你只需要计算对的数量。