リストに重複が含まれているかどうかを調べる最も効率的な方法

Question

大きなサイズの整数のlistが入力として与えられています。 リスト内の項目がすべて異なるかどうかをチェックする関数を記述したいと思います。

アプローチ1：これまでに遭遇したすべてのアイテムをリストに反復し、setを使用して追跡します。重複が発生するとすぐにTrueを返します。

def containsDuplicates1(a): 
    seen = set()         
    for i in a:         
     if i in seen: 
      return True 

     seen.add(i)   

    return False 

時間複雑度：O（N）
空間複雑：O（N）

アプローチ2：setにリスト全体を変換し、その長さを比較します。

def containsDuplicates2(a): 
    return len(a) != len(set(a))     

時間複雑度：O（N）（set(a)動作用）
空間複雑：与えられたリストに含まれている可能性があるときにO（N）

最初のアプローチは、第二のアプローチよりも良好に機能します重複します。

これが最善の方法ですか？あるいは、この問題を解決するために、時間と空間のどちらかに効率的な方法がありますか？

P.S：スタックオーバーフローに関するすべての関連する質問を読みましたが、どれも問題の効率性の側面について議論していません。したがって、私はここにそれを求めました。

Answer 1

これをO（n）よりも時間的にも空間的にも小さくできますか？

すべての要素が異なる場合を考慮してください。これが当てはまることを確認するには、少なくとも1回はすべての要素を調べる必要があります。これにはO（n）時間が必要です。

要素が取ることができる値に制約がない場合、あなたが見たものに対して将来の要素をチェックするために、今まで見たすべての要素を保存する必要があります。すべての要素が異なる場合は、O（n）のメモリが必要です。