0

アイテムの配列があり、一致するアイテム (重複) を見つける必要があります。今のところ、最も単純な O(n^2) アルゴリズムを実行しています。アイテムの種類は関係ありませんが、知りたい場合は画像です。

myarray;   
for(i = 0; i < myarray.length - 1; i++) 
    for(int j = i+1; j < myarray.length; j++) 
        if(myarray[i] = myarray[j]) 
           output(names of items);

ウィキペディアとグーグルを試しましたが、答えは出てきませんでした。任意の言語のリンク、アルゴリズム、またはコードは素晴らしいでしょう。

4

3 に答える 3

1

配列内の重複を見つけるには、リストを並べ替えてスキャンし、 で隣接する同一のアイテムを探しますO(n log n)。重複を出力するだけで、メモリが問題にならない場合は、既に見た要素の hashSet を保持し、配列を調べて、現在の要素がセット内にあるかどうかを確認できます。存在する場合は複製として出力し、そうでない場合はセットに挿入します。それはO(n)

于 2012-05-04T13:11:54.963 に答える
1

アイテムの順序が見つかったら、並べ替えます。次に、アイテムが隣り合っているため、等しいアイテムを見つけるのは非常に簡単になります。

これは O(n*Log(n)) のみです。

于 2012-05-04T13:09:23.760 に答える
1

隣接するアイテムを並べ替えて比較するのではなく、各アイテムを自己均衡二分木に追加してみませんか。これにより、「すでに存在する」チェックが無料で（一種）得られます。

于 2012-05-04T13:12:48.520 に答える