2

我有一个整数列表（从 0 到 N），我需要创建一个新列表，其中包含第一个列表中每个整数的索引。

也就是说，给定

s = [4, 2, 6, 3, 0, 5, 1]

确定r这样s[r[i]] = i

r = [4, 6, 1, 3, 0, 5, 2]

我目前的解决方案是

r = [s.index(i) for i in xrange(len(s))]

有没有更好的办法？

4

5 回答 5

4

我假设每个整数只S出现一次。您当前的解决方案将起作用，问题是s.index执行O(N)搜索，使其成为一项O(N**2)操作。

对于一个大列表，我希望下面的代码更快，因为它是O(N)

# initialise the whole list with some value
r = [-1]*N

for j, s_j in enumerate(s):
    r[s_j] = j

# if any element of r is still -1 then you know it did not appear in s
于 2012-11-09T05:26:10.167 回答
3

看起来字典会更好：

s = [4, 2, 6, 3, 0, 5, 1]
r = dict((v,i) for i,v in enumerate(s))

测试：

>>> for i,_ in enumerate(s):
...     print i, s[r[i]]
... 
0 0
1 1
2 2
3 3
4 4
5 5
6 6
于 2012-11-09T05:20:53.770 回答
2

就个人而言，您展示的方法很棒。

任何一个字典都可以——这将是我的第一次尝试：

r = {v:i for i, v in enumerate(s)}

或者，如果您必须使用列表，另一种方法是：

r = [x[0] for x in sorted(enumerate(s), key=lambda v:v[1])]
于 2012-11-09T05:22:26.223 回答
2

你可以使用numpy吗？

>>> import numpy as np
>>> s = np.array([4, 2, 6, 3, 0, 5, 1])
>>> s.argsort()
array([4, 6, 1, 3, 0, 5, 2], dtype=int64)
于 2012-11-09T05:42:10.583 回答
2

我用 timit 模块 @10^6 次迭代 - 5 次重复做了一个简单的基准测试。

DaveP :       1.16 +/- 0.04s

koblas:       7.02s +/- 0.04s

Jon Clements: 1.82 +/- 0.02s

Zero Piraeus: 6.04 +/- 0.4s

最后但并非最不重要：

r=s[:]
[r[s[i]] for i in s]

我的建议：1.11 +/- 0.03s

于 2012-11-09T06:04:57.797 回答