python - 根据键重新排列列表而不排序

Question

我有一个元组列表 (x, ind) 其中 x 是项目而 ind 是它在结果列表中的目标索引.该列表是随机排列的，但可以假设如果列表中有 N 项，则元组中 ind 的值将在 [ 0,N) 没有重复(即所有有效索引将只存在一次)。如何获取每个元组位置为 ind 的列表？

请不要与许多关于如何按键排序的现有答案混淆。

显然，按 ind 键排序很容易，但是会有不必要的额外 O(n*logn) 成本，而 O 应该是(n) 操作，因为上述关于 ind 值的假设。

所以:

l = [('item1',1), ('item0',0), ('item2',2), ('item4',4), ('item3',3)]
l2 = magic_rearrange(l, key=lambda x: x[1])
print(l2)

应该给:

[('item0',0), ('item1',1), ('item2',2), ('item3',3), ('item4',4)]

Answer 1

假设您的索引是唯一的，这是一种方法。您可以初始化一个新列表，然后将元素插入到正确的位置。

def magic_rearrange(l1):
    l2 = [None] * len(l1)
    for i in l1:
        l2[i[1]] = i
    return l2

还有一个演示:

>>> l = [('item1',1), ('item0',0), ('item2',2), ('item4',4), ('item3',3)]
>>> magic_rearrange(l)
[('item0', 0), ('item1', 1), ('item2', 2), ('item3', 3), ('item4', 4)]

---

如果您使用 numpy 的精美索引，有一种更快的方法可以做到这一点。

import numpy as np
def magic_rearrange(l1):
    l2 = np.repeat(None, len(l1))
    l2[[x[1] for x in l1]] = l1
    return l2

还有一个演示:

>>> magic_rearrange(l)
array([('item0', 0), ('item1', 1), ('item2', 2), ('item3', 3), ('item4', 4)], dtype=object)