8

それらを並べ替えてから、各要素を1つずつ確認することも考えられますが、これはnlognです。リスト内の個別の要素をカウントする線形の方法はありますか？

4

3 に答える 3

11

更新：-明確な対ユニーク

「一意の」値を探している場合（要素「JASON」が複数回表示されている場合のように、一意ではなくなっているため、カウントしないでください）

HashMapを使用すると、線形時間でそれを行うことができます;）

（一般化された/言語に依存しないアイデアはハッシュテーブルです）

HashMap / Hashテーブルの各エントリは<KEY, VALUE>ペアであり、キーは一意です（ただし、ペア内の対応する値に制限はありません）。

ステップ1：

リスト内のすべての要素を1回繰り返します：O（n）

  • リストに表示されている各要素について、それがすでにO（1）にあり、償却されているかどうかを確認します。
    • そうでない場合は、リスト内の要素の値をKEYとして、この値をVALUE O（1）まで表示した回数を指定してHashMapに追加します。
    • もしそうなら、あなたがこれまでにこのキーを見た回数を増やしてくださいO（1）

ステップ2：

HashMapを反復処理し、VALUEが正確に1（したがって一意）に等しいKEYSをカウントしますO（n）

分析：

  • ランタイム：O（n）、償却
  • スペース：O（U）。ここで、Uは個別の値の数です。

ただし、 「異なる」値を探している場合（たとえば、異なる要素の数を数えたい場合など）、HashMap / Hashテーブルの代わりにHashSetを使用してから、HashSetのサイズを照会するだけです。

于 2012-12-13T17:22:52.547 に答える
1

この非常にクールなO（n）時間およびO（1）スペースのインプレースアルゴリズムを適応させて、重複を削除し、個別の値をカウントするタスクに適用できます。最終的なOの番兵値に等しい値の数をカウントするだけです。 （n）合格し、リストのサイズからそれを減算します。

于 2012-12-13T17:46:04.030 に答える
0

リストのすべての要素をHashSetに追加してから、HashSetのサイズ（カーディナリティ）を確認します。これは、リスト内の個別の値の数です。

于 2012-12-13T17:54:13.513 に答える