0

私を困惑させる割り当て演習：

nランダムな順序の整数の配列があり、演習では、以下に指定された方法を使用してそれらを並べ替える必要があります。

まず、次の 2 つの規則に従って整数を行に配置します。

  1. a < b の場合にのみ、整数 a を整数 b の上に配置します
  2. それ以外の場合、整数 a を新しい行に配置します

これらの 2 つのルールは、配列の並べ替えに使用されます。ルールの適用が終了したら、小さい方の可視整数を、ソートされるまで一度に 1 つずつ選択します。

この演習では、3 つの配列を使用する必要があります。

  1. data[1...n]ソートする数値を含む
  2. column[1...n,1...]
  3. number[1..n]各列の整数の総数を表します

たとえば、

data = [3,2,12,8]

次にcolumn、次のようになります。

column[1,1] = 3
column[2,1] = 2
column[1,2] = 12
column[2,2] = 8

そしてnumberなるだろう[2,2]

ループを作成しようとしています (英語の擬似コードは、自然言語で学習しているものとは異なる可能性があることに注意してください)

for counter=1 to n 
    number[counter]:=0;
end for

for counter=1 to n
    a := 1;
    b := 1;

    if data[counter] < column[a,number[b]] or number[b]=0 then
        number[b] := number[b] + 1;
        column[a,number[b]] := data[counter];
    else 
        a:=a+1;
        b:=b+1;
    end if
end for

しかし、このコードには多くの間違いがあります。誰かがロジックのどこが間違っているかを説明してもらえますか?

4

1 に答える 1

0

最終的にいくつ使用するかわからないためrows、拡張可能なデータ構造を使用して を表す必要があるrowsため、リストを使用します。次に、rowsは数字を積み重ねているため、各行は積み重ねである必要があります。お気に入り

List<Stack<Integer>> rows = new ArrayList<Stack<Integer>>();

その後、アルゴリズムは O(n^2) になります。入力をループして、行に追加します。

for(int i: input){
   boolean done = false;
   for(int x=0; x < rows.size() && ! done; i++)
     if(row.peep() > i){
       row.add(i);
       done = true;
     }
   if(!done)
     row.add(i);
}

行への入力が完了したら、次のステップは整数を読み戻すことです。ここから取れるはずです。

于 2013-01-15T23:13:05.663 に答える