重排列表不排序

我有元組(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

重排列表不排序

回答

相關問題