重新排列列表基于键而不排序

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)