5

17,000 語を含む ArrayList があります。リストに単語がまだ含まれていない場合にのみリストに単語を追加する必要があり、リストの並べ替え順序を保持する必要があります。つまり、アルファベット順に正しい場所に配置する必要があります。

挿入する正しい場所を見つける方法がわかりません。バイナリ検索を使用して、単語が既にリストにあるかどうかを調べています。リストにある場合はインデックスを返し、そうでない場合は -1 を返します。ArrayList.add(int index, E element) を使用して入れることを計画していました。

4

6 に答える 6

2

組み込みのbinarySearch方法を使用します。キーが見つからない場合、返される番号は
-(insertionIndex) - 1

于 2012-05-08T00:02:32.207 に答える
1

二分探索が思い浮かびますが、リストAPIにはより良いものが含まれている可能性があります

二分探索では、上と下に 1 つずつ、合計 2 つのアイテムが残っているポイントに到達します。そのうちの 1 つはアイテムに対して == である可能性があります。あなたのケースでは == ケースがないので、より高いインデックスのインデックスを返し、その位置に挿入します。Java にタプル クラスがあるかどうか、またはコンテナーを構築できるかどうかはわかりません。いずれにせよ、次のようなものを返します。

(bool, int) binSearch(IList list)
  returns true, -1 if found
  returns false, higher of 2 bounds otherwise

明らかにこれはJavaではありませんが、変換するのは簡単ではありません

于 2012-05-07T23:42:13.603 に答える
1

二分探索を記述した場合、最後に検索された値を返すように修正できます。この値は、一致する文字列の場所または挿入する場所のいずれかです。

つまり、バイナリ検索では、文字列が見つかるか、それ以上細分化できなくなるまで、リストを細分化します。リストを細分化できなくなった位置は、文字列を挿入する位置です。

于 2012-05-07T23:55:29.037 に答える
0

プロセスを固定するために、一般的な考え方は、私たち全員が知っているように、より多くのメモリを使用することです。ここでは、各文字の最初の文字列のインデックスにすることができます。たとえば、追加のArrayListは、疑似で記述します。

ArrayList indexes;
indexes[0] = {"a", 0};
indexes[1] = {"b", 123};
...

「a」で始まる文字列の場合、インデックス0〜123の間でバイナリ検索を実行できます。

于 2012-05-08T00:02:07.273 に答える
0

あなたが言うように、繰り返される単語がない場合は、triの実装を検討できます。トライに対する挿入操作は、衝突がないため、ハッシュ テーブルよりもいくらか高速です。検索についても同様です。

さらに、ArrayListリストの途中に要素を挿入するには、要素の半分を再配置するか、配列サイズを大きくする必要があり、多少コストがかかる可能性があります。

興味がある場合は、次のページで実装を確認できます: https://forums.oracle.com/forums/thread.jspa?messageID=8787521

于 2012-05-08T00:10:01.483 に答える