重排列表不排序

我有元组(x, ind)的一个列表，其中x是项目，ind是它在结果列表中的目标指数。该列表以随机顺序排列，但可以假设如果列表中有N项目，则元组中的ind的值将在[0,N)内而没有重复（即，所有有效索引将只存在一次）。我如何获得一个列表，其中每个元组的立场是ind？重排列表不排序

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

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

所以：

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)]

来源

2017-06-20 Stav

这仍然是排序，但没有'排序'功能。 –

假设你的指数是独一无二的，这里有一个方法。您可以初始化一个新的列表，只需在正确的位置插入元素。

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)

来源

2017-06-20 12:26:39

该死的你打我吧，美观大方。 – Wboy

这是好事，但它并没有考虑不同的密钥。虽然它可能解决OP的问题:) –

@ReutSharabani是......如果OP真的需要密钥，我会支持你的解决方案。 –

首先创建列表，然后替换：

def magic_rearrange(l, key): 
    # creates list to not change original list 
    new_list = list(l) 
    # reorder on new list 
    for original_index, new_index in enumerate(map(key, l)): 
     new_list[new_index] = l[original_index] 
    return new_list

来源

2017-06-20 12:27:03

您应该为完整性添加默认参数！ –

在这里你去。

def magic_rearrange (input_list, key = lambda x: x): 
    result_list = [None] * len (input_list) 
    for p in input_list: 
     result_list[key (p)] = p 
    return result_list

我们只是创建一个所需长度的列表，然后把每个元素放在它的位置。操作的顺序可以是任意的，但每一个元素最终将获得其在结果列表中的位置。这是O（N），如果复制单个列表元素，并取得密钥均为O（1）。 key = lambda x: x是默认的顺序，它是比较整个元素（但无用，因为结果只是list(range(N))）。

来源

2017-06-20 12:30:31 Gassa

重排列表不排序

回答

相关问题