リスト内の要素の集合をPythonでソートせずに見つけ出す

Question

私は要素1、...、Kの繰り返しを持つリストを持っています。 K = 4のための例：

[4 2 1 1 2 1 1 3 2 ] 

私は1、...、Kは（並べ替えなし）のリストに登場していることシーケンスを見つけたいです。上記のシーケンスの例では、結果は私はあまりランタイムと、pythonで効率的にこのアルゴリズムを書くことができますどのように

[4, 2 ,1 ,3 ] 

だろう。

ありがとうございました！

Answer 1

範囲1内のすべての数字は、...、kを通り（表示されていることを前提として別の方法であります問題の説明）：

def inOrder(nums): 
    k = max(nums) 
    indices = [nums.index(n) for n in range(1,k+1)] 
    return [n for i,n in sorted(zip(indices,range(1,k+1)))] 

例えば

>>> inOrder([4, 2, 1, 1, 2, 1, 1, 3, 2]) 
[4, 2, 1, 3] 

それはnは番目であるO(nk) eリストの長さ。一方、組み込みのメソッドを使用するのはかなり速く、平均して各数値の最初の出現がリストの中でいくらか早い場合、ランタイムは最悪の場合よりもはるかに優れています。たとえば、ユーザーが定義した場合：

nums = [random.randint(1,1000) for i in range(10**6)] 

は、 inOrder(nums)の評価は、（リストは100万個のエントリを持っているにもかかわらず）秒未満かかります。

Answer 2

通常のリスト-重複除去は、おそらく十分でしょう：

def f7(seq): 
    seen = set() 
    seen_add = seen.add 
    return [x for x in seq if not (x in seen or seen_add(x))] 

reference

しかし、これは自然O(N)です。これは一般的なケースで可能な最高のものですが、は、大量のインプットに対して実用的な立場からよりうまくやることができます。

def ordered_dedupe_with_constraints(lst, K): 
    output = collections.OrderedDict() 
    len_lst = len(lst) 
    i = 0 
    while len(output) < K and i < len_lst: 
     output.setdefault(lst[i], None) 
     i += 1 
    return list(output) 

この第二の答えは、あなたがk番目の要素が出力に追加されたとき、早期に破損するlst中で最もK異なる要素を持っているという事実を使用しています。これはまだ一般的なケースではO(N)ですが、これより多くのパフォーマンスが得られる可能性があります。K << len_lstであり、アイテムが十分にシャッフルされています。もちろん、Kを事前に知っておいて、maxを取得するための反復処理以外の手段をとる必要があります（これは、短絡の目的を無効にします）。

これらの制約が当てはまらない場合は、実装がここの実装よりも最適である可能性が高いため、参考文献に報告されている関数f7の方が良いでしょう。

Answer 3

from collections import OrderedDict 
list_numbers=[4,2,1,1,2,1,1,3,2] 
print list(OrderedDict.fromkeys(list_numbers)) 

これは、所望の出力を与える - [4、2、1、3]ここ

Answer 4

これはO（k）になります。

リストを通過します。各要素について、その要素が初めて表示された場合は、それがリストに追加されます。

リストにkやその他の非整数要素より大きい数値がある可能性がある場合は、kより小さい整数であることをチェックします。このコードは、0とkの間のすべての数字がリストに存在することを保証するものではありません。

def findSeq(inputList): 
    dict = {} 
    newList = [] 
    for elem in inputList: 
     if elem not in dict: 
      dict[elem] = True # This can be set to anything 
      newList += [elem] 
    return inputList 

私はあなたの質問を誤解していたため、これを最初に書きました...それは無駄にしたくないからです:)。これにより、リストの要素が別のリストに順番に表示されるかどうかがチェックされます。

# inList([2, 1, 5], [2, 3, 1, 5]) -> True 
#inList([2, 1, 5], [2, 3, 5, 1]) -> False 

def inList(small, big): 
    i = 0   # index in small 
    j = 0   # index in big 
    while j < len(big): 
     if small(i) == big(j): 
      i += 1 
      j += 1 
      # Any success is guaranteed to happen here, 
      # right after you've found a match 
      if i+1 == len(small): 
       return True 
     else: 
      j += 1 
    return False