ソートなしでキーを並べ替えるリスト

Question

私はタプルのリストを持っています(x, ind)ここでxはアイテムで、indは結果のリストのターゲットインデックスです。リストはランダムな順序ですが、リストにNの項目がある場合、タプル内のindの値は、繰り返しなしで[0,N)になります（つまり、有効なインデックスはすべて1回だけ存在します）。各タプルの位置がindのリストを取得するにはどうすればよいですか？

キーでソートする方法の多くの既存の回答と混同しないでください。

もちろん、indキーでソートすることは簡単ですが、理由はind値に関する前述の仮定のO(n)操作がどうあるべきかに不必要な余分なO(n*logn)費用があるでしょう。

だから、

：

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) 

Answer 2

最初のリストを作成し、交換してください：

ここ

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 

Answer 3

あなたが行きます。

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（1）である場合、これはO（N）です。 key = lambda x: xはデフォルトの順序であり、要素全体を比較しています（ただし、結果はちょうどlist(range(N))なので役に立たない）。