0

クライアントが整数配列を作成し、要素がこの配列にあるかどうかを挿入、削除、およびチェックできるようにするJavaの非常に単純なクラスに取り組んでいます。クラスの制限の 1 つは、配列を常に昇順で並べ替える必要があることです。要素が挿入されるたびにinsert(int x)メソッドがプライベートソートメソッドを呼び出すのは効率的ですか、それとも別のアプローチがありますか?

4

5 に答える 5

1

配列でなければならない場合は、バイナリ検索を実行して挿入ポイントを見つけ、より高い値の要素を 1 つ上に移動してから、新しい要素を開いたギャップに配置するのが最善の方法です。

これは、挿入ごとに平均して配列要素の半分を移動します。

別のデータ構造を使用するオプションがある場合は、キーが挿入する整数で、値が要素が挿入された回数のカウントである TreeMap をお勧めします。

于 2013-03-30T17:59:49.983 に答える
0

SortedSet< Integer > (実装クラスTreeSet )のようなソートされたコレクションを使用することをお勧めします。

常にソートして重複を削除します。

絶対に必要な場合はint[]、java.util.Arraysユーティリティにsearchとsortが含まれています。

于 2013-03-30T17:58:31.807 に答える
0

Java 配列のサイズは固定されています。削除と挿入を行う必要がある場合は、おそらくリスト (ArrayList または LinkedList) が必要です。

いくつかの代替案:

  1. リスト; 各挿入に対してバイナリ検索を実行して、挿入ポイントを見つけます。

  2. リストとマップ。リスト内の各整数の（最初の）インデックスを示すマ​​ップを保持します。

  3. リスト; 挿入に加えてCollections.sort(list)

1 はそれほど単純ではありませんが、最も有益です。2 は速度の点で最も効率的ですが、スペースを浪費します。3 は最も単純で実用的です。

于 2013-03-30T18:01:18.967 に答える
0

要素が挿入されるたびに配列をソートする方法

このようにしてください

 Arrays.sort(array);

指定された int の配列を昇順で並べ替えます。ソート アルゴリズムは調整されたクイックソートであり、Jon L. Bentley と M. Douglas McIlroy の「Engineering a Sort Function」、Software-Practice and Experience、Vol. 23(11) P. 1249-1265 (1993 年 11 月)。このアルゴリズムは、多くのデータ セットで n*log(n) パフォーマンスを提供するため、他のクイック ソートでは 2 次パフォーマンスに低下します。

ここでJavaドキュメントを読んでください。

Array の代わりに実行時に項目を拡大するには、ArrayList を使用します。

arrayList でこのようにします。

List<String> unsortList = new ArrayList<String>();
unsortList.add("111");
unsortList.add("333");
unsortList.add("222");

//before sort
System.out.println("ArrayList is unsort");
for(String temp: unsortList){
    System.out.println(temp);
}

//sort the list
Collections.sort(unsortList);

//after sorted
System.out.println("ArrayList is sorted");
for(String temp: unsortList){
    System.out.println(temp);
}
于 2013-03-30T17:54:06.887 に答える