0

宿題のために、配列を並べ替えることができるメソッドを書く必要があります。並べ替えメソッドはできるだけ効率的でなければなりません。

  1. 配列の先頭には、4 で割り切れるすべての数値が表示されます。
  2. 4 で割り、余りが 1 になるすべての数字が続きます。
  3. 4 で割り、余りが 2 になるすべての数字が続きます。
  4. 配列の最後には、他のすべての数値 (残りの 3 で 4 で除算される数値) があります。

このセットを試してみました 4 つのポインター:
2 つのポインター 最初は 0 と 1
の残り 2 と 3 の残りの配列の最後の 2 つのポインター

これは私がこれまでに見つけたものです（もちろん問題があります）、助けていただきありがとうございます！

public static void sortByFour (int[] arr)
{
    int temp;
    int noRemainderIndex = 0;
    int remainder1Index = 1;
    int remainder2Index = arr.length - 2;
    int remainder3Index = arr.length - 1;

    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] % 4 == 0)
        {
            temp = arr[noRemainderIndex];
            arr[noRemainderIndex] = arr[i];
            arr[i] = temp;
            noRemainderIndex++;
            remainder1Index++;
        }
        else if (arr[i] % 4 == 1)
        {
            temp = arr[remainder1Index];
            arr[remainder1Index] = arr[i];
            arr[i] = temp;
            remainder1Index++;
        }
        else if (arr[i] % 4 == 2)
        {
            temp = arr[remainder2Index];
            arr[remainder2Index] = arr[i];
            arr[i] = temp;
            remainder2Index--;
        }
        else if (arr[i] % 4 == 3)
        {   
            temp = arr[remainder3Index];
            arr[remainder3Index] = temp = arr[i];
            arr[i] = temp;
            remainder3Index--;
            remainder2Index--;
        }
    }
4

4 に答える 4

2

宿題のヒント。

  1. 既存のライブラリ メソッドの使用が許可されている場合はArray.sort(...)、Comparatorインターフェイスを参照してください。(プリミティブ型の配列を並べ替えるときにカスタム コンパレータを使用するには、最初にラッパー型に変換する必要があることに注意してください。たとえば、変換int[]、Integer[]並べ替え、元に戻すなどです。)

  2. 使用が許可されていないArray.sort(...)(または同様の) 場合は、これが並べ替えの問題なのか照合の問題なのかを判断してください。つまり、4 つのカテゴリの番号を並べ替える (または順序を保持する) 必要がある場合です。

  3. 4 つの一時配列を使用して問題を単純化することもできますが、配列を複数回通過させて要素のペアを交換することを含む他の (よりトリッキーな) 解決策があります。

  4. 解決する必要がある問題の 1 つは、4 つのカテゴリのそれぞれにいくつの数字があるかを事前に知らないということです。そのため、数値の移動先が事前にわかりません。しかし、これには解決策があります...

...ソート方法は可能な限り効率的でなければなりません。

これは宿題の要件ですか、それともあなたの要件ですか?

これが自分で追加したものである場合、注意してください - あなたのマーカーは、(おそらく) より効率的だが過度に複雑な解決策よりも単純な解決策に高い評価を与える可能性があります。

優れたソフトウェア エンジニアは、すべてのプログラムで究極の効率を追求するわけではありません。むしろ、彼はさまざまなことのバランスをとっています。

  • 機能要件、
  • パフォーマンスの要件、
  • ソフトウェアの保守性の要件、および
  • プロジェクトの締め切り、

これらの要件の一部は暗示されている可能性があり、および/または経営陣によって適切に理解されていない可能性があることに注意してください。

(または別の言い方をすれば、プログラムは高速ですが、確実に動作しない、保守できない、準備が間に合わないなどのプログラムは失敗です。)

一方、パフォーマンスがこの宿題の課題の要件である場合、講師は Java で小さなプログラムのパフォーマンスを測定する方法を説明しているはずです。(私を信じてください...これは簡単なことではありません。)これを宿題の問題に適用して、どの代替ソリューションが最速かを判断する必要があります。

于 2012-05-26T16:03:54.783 に答える
0

これを行うためのより良い方法は、ケースごとに1つずつ、4つの配列を持つことだと思います。各配列をキューとして扱います。配列を反復処理し、それぞれの配列にプッシュします。それが完了したら、配列を互いに追加するだけです。非常にクリーンなソリューション。

于 2012-05-26T16:03:28.337 に答える
0

クイックソートで使用されるパーティションアルゴリズムに似たものが必要だと思います。

4つの ポインターは良い 出発
点ですが、それらの機能を変更させてください。未分類の


配列は 5 つの部分に分割されます: 残り = 0、1、2、3、および未分類。

剰余 = 3 の場合、ポインター 4 をインクリメントするだけです。剰余 = 3 グループに含まれる場合の数。
剰余 = 2 の場合、ポインター 3 をインクリメントし、現在の値をポインター 3 の値と交換します。ポインター 4 をインクリメントします。
剰余 = 1 の場合、ポインター 2 をインクリメントし、現在の値と交換します。ポインター 3 をインクリメントし、現在の値と交換します。ポインター 4 をインクリメントします。
剰余 = 0 の場合は、スワップを 3 回行います。

于 2012-05-26T16:20:04.117 に答える
0

数値と剰余の 2 つの値を保持するカスタム クラスを作成してみませんか。このミニ クラスの配列を作成し、値を渡し、残りを事前に計算します。これにより、リストの要素を通過するたびに残りを再計算する必要がなくなります。残りのプロパティに基づいて要素を移動および並べ替える必要があります。

次に、一意の要素がほとんどないリストを並べ替えるという古典的な問題があります。選択する並べ替えアルゴリズムのパフォーマンスは、初期条件によって異なります。最良のオプションは、Shell ソート アルゴリズムまたは Quick3 であると言えます。

http://www.sorting-algorithms.com/few-unique-keys

于 2012-05-26T16:15:24.107 に答える