3

製品名の非常に長いリストが与えられた場合、一意である最初の製品名を見つけます（1回だけ発生します）。ファイル内で反復できるのは1回だけです。

ハッシュマップを取得して、（keys、count）を二重にリンクされたリストに格納することを考えています。基本的に、リンクされたハッシュマップは誰でもこれを最適化するか、より良いアプローチを与えることができます

4

3 に答える 3

2

リストを繰り返すことができるのは1回だけなので、保存する必要があります

  • 出力になる可能性があるため、1回だけ発生する各文字列
  • リスト内の相対的な位置
  • 複数回出現する各文字列（または、恐れていない場合はそれらのハッシュ）

特に、複数回発生する文字列の相対位置を保存する必要はありません。

あなたが必要です

  • 文字列のセットの効率的なストレージ。ハッシュセットは適切な候補ですが、文字列のセットによっては、トライの方が圧縮率が高くなる可能性があります。
  • 値による効率的なルックアップ。これにより、ベアリストが除外されます。ハッシュセットが明らかに勝者ですが、トライもうまく機能します。トライの葉をハッシュセットに保存できます。
  • 最小値の効率的なルックアップ。これにより、リンクリストが要求されます。

結論：

文字列のセットにリンクされたハッシュセットを使用し、それらが一意であるかどうかを示すフラグを使用します。あなたが記憶のために戦っているなら、リンクされたトライを使用してください。リンクされたトライが遅すぎる場合は、検索のためにトライの葉をハッシュマップに保存します。リンクリストには一意の文字列のみを含めます。

全体として、ノードは次のようになります。Node:{Node[] trieEdges, Node trieParent, String inEdge, Node nextUnique, Node prevUnique}; Node firstUnique, Node[] hashMap

実装を容易にするために努力する場合は、代わりに2つのハッシュセットを使用できます（1つはリンクされています）。

于 2013-01-16T17:56:47.007 に答える
0

リンクされたハッシュマップを使用することは十分に明白です。それ以外の場合は、文字列がカウント順に並べられているTreeMapスタイルのデータ構造を使用できます。したがって、入力の読み取りが完了するとすぐに、一意の文字列が存在する場合、ツリーのルートは一意になります。リンクされたハッシュマップとは異なり、挿入にはO（n）ではなく最大でO（log n）が必要です。基本的なTreeMapを必要なものに拡張する方法については、TreeMapsを参照してください。また、リンクされたハッシュマップでは、最初の一意のキーを見つけるためにO（n）を移動する必要がある場合があります。TreeMapスタイルのデータ構造を使用すると、ルックアップはO（1）（ルート）になります。より多くの一意のキーが存在する場合でも、最初に遭遇したキーがルートになります。後続のものはルートの子になります。

于 2013-01-17T16:03:17.377 に答える
0

次のアルゴリズムは、O（N + M）時間でそれを解決します。どこ

N=文字列の数

M=すべての文字列にまとめられた文字の総数。

手順は次のとおりです。

`1. Create a hash value for each string`

`2. Xor it and find the one which didn't have a pair`

Xorには、xor a=0およびbxor0=bを実行する場合にこの便利なプロパティがあります。

文字列のハッシュ値を生成するためのヒント：27の基数システムを使用し、aa値1、ba値2などをzが26になるまで指定します。したがって、文字列が「abc」の場合、ハッシュ値を計算します。 as：H = 3 *（27 power 0）+ 2 *（27 power 1）+ 1（27 power 2）= 786モジュラス演算子を使用して、ハッシュ値を32ビット整数に収まるように小さくすることができます。衝突に注意してください。衝突は基本的に2つの文字列であり、異なるものの、モジュラス演算のために同じハッシュ値を取得します。ほとんどの場合、あなたはそれを必要としないだろうと思います。

したがって、各文字列のハッシュを計算し、最初のハッシュから開始して排他的論理和を続けると、結果にはペアを持たない文字列のハッシュ値が保持されます。 注意：これは、文字列がペアで発生する場合にのみ役立ちますが、最初はこれをお勧めします。そのため、私はそれに答えました。

于 2013-01-16T17:56:48.450 に答える