最近、次のような質問を見つけました。
"Given an array of strings, return the number of distinct strings in that array."
私はこの解決策を思いついた：
1. Get number_of_strings, which equals the number of strings in the input array
2. Get number_of_non_redundant, which equals the length of the input array cast as a set
3. Return 2 times number_of_non_redundant - number_of_strings
だから、私の質問は、このアルゴリズムはすべてのデータセットで機能しますか？
文字列の配列を考えてみましょう["a", "a", "a", "d", "d", "d"]。
number_of_strings6です。number_of_non_redundantは2です。あなたは戻ることを提案し2 * 2 - 6 = -2ます。つまり...いいえ、アルゴリズムはすべてのデータセットで機能するわけではありません。
しかし、私が問題を大いに誤解していない限りnumber_of_non_redundant、それはあなたが返したいものの定義であるため、戻るだけで常に機能します。:)
他の人が指摘しているように、単に戻るnumber_of_non_redundantことはこの問題への答えのようです。
決定するための可能な解決策は次のnumber_of_non_redundantとおりです。
1）ハッシュセットを作成します（言語固有）
2）配列全体を反復処理し、配列の各要素で、要素がハッシュセットに存在するかどうかを確認し、存在しない場合は追加します。
3）ハッシュセットのサイズを返します。
ここでハッシュセットを使用すると、定数時間の操作（追加、含む）が提供されます。
さらに、配列をセットに単純にキャストすることはできないことを指摘したいと思います（少なくとも私はこれを言語で認識していません） 。キャスティングは一定時間の操作です。これらは2つの異なるデータ構造であり、配列から要素を取得してセットに配置するには、配列を反復処理して要素をセットに入力する必要があります。
最初に配列を辞書式に並べ替えてから、要素i番目と（i-1）番目の間の変更を追跡するフラグ変数を使用して配列をループするのはどうですか？
このアルゴリズムは、すべてのデータセットで機能するわけではありません。ただし、特定の例では機能する可能性があります。
say n = number of non redundant strings
p = number of strings in original array
あなたによると2n-p = n => n= p
アルゴリズムが機能するの(number of non redundant strings = length of original array)は、元の配列がセットである場合のみです。
ヒントを与えるために、これを解決する理想的な方法は、十分なメモリが利用可能であるか、Sortingを使用してその場で実行できるが、ハッシュに比べて時間がかかる場合にハッシュすることです。