0

このレベルまで分析して一般化した問題があり、効率的なパフォーマンスのために解決する必要があります

1_A_B、2_A、2_B、2_A_C、1_C、1_B、2_B_C などのデータベースからアイテムの膨大なコレクションを取得します..

ユーザーがAを選択すると (数値が返されることに基づいてアルファベットのみを選択できます)、2_A が存在するため2を取得する必要があります。つまり、A を選択すると 2 が表示されます。

ユーザーがBを拾うと2,1の両方が得られ、 B_C を拾うと2しか得られません

入力順はランダムです。最適なメモリ使用量を維持しながら最高のパフォーマンスを得るには、どのデータ構造をどのように効率的に設計する必要があるか

で行こうと思ったのMap<Alphabets,List<Numerics>>ですが、数値を示すアルファベットの組み合わせは簡単ではありません[B_CとC_Bは同じ結果を返すはずで、アルファベットの組み合わせはたくさんあります]

4

2 に答える 2

2

これが問題の良い解決策になるかどうかはわかりませんが、アルファベットがかなり限られている場合は、各アルファベットを解析して 2 の累乗に変換します。

たとえば、私は割り当てます

A = 1 (2^0)
B = 2 (2^1)
C = 4 (2^2)
D = 8 (2^3)

.. 等々。

次に、HashMap<Integer, List<Integer>>データを保存するために使用します。HashMap では、キーはアルファベットの数値の合計であり、値はデータのプレフィックスである数字のリストになります。

たとえば1_A_B, 2_A, 2_B, 2_A_C, 1_C, 1_B, 2_B_C、

1_A_B は map[3, {1}] の下に保存され、2_A は map[1, {2}] の下に保存されます。したがって、特定のデータセットのマップは次のようになります

3, {1} //1_A_B
1, {2} //2_A
2, {2, 1} //2_B , 1_B
5, {2} //2_A_C
4, {1} //1_C
6, {2} //2_B_C

入力 B_C が入力されると、値 6 (B+C) を持つキーを検索するだけで、答えとして 2 を返すことができます。

上記の方法は、B_C と C_B の合計が同じであるため、B_C と C_B を扱う状況でもうまく機能します。

于 2013-02-19T05:23:11.430 に答える
1

私は

HashMap<String,Integer>

、まばらなデータに適しています。文字列を入力する前に、解析して並べ替えます。このように、B_C と C_B は同じと見なされます。
存在を確認するときは、確認の前に解析と並べ替えも行います。

編集: 入力ごとに、ハッシュ テーブルに 1 つの要素を格納します。例: 3_C_A は、次のように分割して並べ替えた後に入力する必要があります。

<"AC",3>

たとえば「C」の存在を確認するには、ハッシュ マップのキーを検索する必要があります。

Pseudo-code
Foreach(key in hash.keys) {
    Print hash(key) if x found in key
}

メモリ使用量: O(n)
検索パフォーマンス: O(n)

于 2013-02-19T05:06:10.473 に答える