私は、私のWebサービスに送られる大きな整数のリストを持っています。私たちのビジネスルールは、これらの値が一意でなければならないと述べています。重複があるかどうかを判断する最も効果的な方法は何ですか？私は値を知る必要はありません、私は値の2つが等しいかどうかを知る必要があります。整数のコレクションで存在を確認する最も効果的な方法は何ですか？
最初に私は、整数とlist.Exists（）メソッドのジェネリックリストを使用して考えていたが、これはO（n）のです。
次に、DictionaryとContainsKeyメソッドを使用することを考えていました。しかし、私はキーが必要です、私は値を必要としません。そして私はこれも線形検索だと思う。
は、リスト内の一意性を見つけるために使用するより良いデータ型はありますか？それとも、私は線形検索で悩んでいますか？使用HashSet<T>：
HashSetのクラスが 高性能セット操作を提供します。セットは、重複 要素、および要素でない 特定の順序で
HashSet<T>もa constructor that accepts an IEnumerable<T>を露出を含まない コレクションです。 HashSet<T>'sコンストラクタにごList<T>を渡すことによって、あなたはあなたの元List<T>から項目の明確なシーケンスを含む新しいHashSet<T>を参照してしまいます。
あなたは、フレームワーク3.5を使用している場合は、HashSetコレクションを使用することができます
... Hashsetのための仕事のようですね。
そうでない場合は、最良のオプションはDictionaryです。各アイテムの価値は無駄になりますが、それはあなたに最高のパフォーマンスを与えるでしょう。
後でカウントする代わりに項目をHashSet/Dictionaryに追加するときに重複をチェックすると、重複がある場合はO（n）よりもパフォーマンスが向上します。最初の複製を見つける。
数の集合は、他の人がHashSetのを使用することをお勧め続いて、まばらである場合。
しかし、数字のセットが時折ギャップが順番に、ほとんどの場合、あなたが始めるのソートされた配列またはバイナリツリーとして設定された数、最後のペアを格納した場合、それは多くの方が良いだろう。次に、検索キーより小さい最初の値を持つペアを検索し、そのペアの終了値と比較して、セットに存在するかどうかを調べることができます。私はこれのパフォーマンスについて疑問
list.Distinct().Count() != list.Count()
：やってはどう
。私はそれがO（n）と同じくらい良いと思うが、コードは少なくても読みやすい。
inputList.Count！= hashSet.Count、 "ヒューストン、私たちに重複があります！" – user7116
これはまだO（n）ですが、彼が得ることができる最高のものです。 – Marc
@sixlettervariables - 優れた点！ –