5

たとえば、配列がありX[n] = {X0, X1, X2, ... Xn} ます。目標は、すべてのペアの差が昇順になるようにこの配列をソートすることです。

例えばX[] = {10, 2, 7, 4}

答えは次のとおりです。

2 7 10 4
4 10 7 2

私はいくつかのコードを持っていますが、それはブルートフォースです:)

#include <stdio.h>

int main(int argc, char **argv)
{
    int array[] = { 10, 2, 7, 4 };
    int a[4];

    for(int i = 0; i < 4; i++){
        a[0] = array[i];

        for(int j = 0; j < 4; j++){
            a[1] = array[j];
            if(a[0] == a[1])
               continue;

            for(int k = 0; k < 4; k++){
                a[2] = array[k];
                if(a[0] == a[2] || a[1] == a[2])
                    continue;

            for(int l = 0; l < 4; l++){
                a[3] = array[l];
                if(a[0] == a[3] || a[1] == a[3] || a[2] == a[3])
                    continue;
                if(a[0] - a[1] < a[1] - a[2] && a[1] - a[2] < a[2] - a[3])  
                    printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
             }
         }
     }
   }
    return 0;
 }

「きれいな」アルゴリズムのアイデアはありますか? :)

4

3 に答える 3

2

免責事項 このソリューションは、絶対値によって差が大きくなるようにアイテムを配置します。@Will NessへのThx

the difference between every pair is in ascending order要件に応じた 1 つのソリューション。

配列を O(n)*log(n) の昇順でソートし、途中から開始するだけです。そして、次のような要素を配置します:

[n/2, n/2+1, n/2-1, n/2+2, n/2-2, n/2+3 ...]（n / 2）番目の要素の右側にさらに要素がある場合、最初に+1に移動します

[n/2, n/2-1, n/2+1, n/2-2, n/2+2, n/2-3 ...]それ以外の場合は、最初に -1 に移動します。

ここでは、昇順のペアごとの差を取得します。

ノート！！！このアルゴリズムが最小の差を見つけて開始することは保証されていませんが、これが要件であるとは思いません。

例

ソートされた配列:{1, 2, 10, 15, 40, 50, 60, 61, 100, 101}

次に、50 (10/2 = 5)、60 (10/2 + 1 = 6)、40 などを選択します...

あなたは得るでしょう：{40, 50, 15, 60, 10, 61, 2, 100, 1, 101}

どちらがあなたに違いをもたらしましたか：10, 35, 45, 50, 51, 59, 88, 99, 100

于 2013-03-31T09:16:32.780 に答える
2

どれどれ。例の配列は {10,2,7,4} で、表示される答えは次のとおりです。

2 7 10 4         
 5 3  -6     differences,  a[i+1] - a[i]

4 10 7 2
 6 -3 -5

ここでは反転した違いを示します。その方が分析しやすいです。

したがって、目標は、違いa[i+1] - a[i] を降順で取得することです。明らかに、いくつかの正の差分値が最初に表示され、次に負の値が表示されます。これは、配列の最大要素が中間のどこかに現れることを意味します。その左側の正の差は絶対値の降順でなければならず、右側の負の差は絶対値の昇順でなければなりません。

別の配列を例に取りましょう: {4,8,20,15,16,1,3}。並べ替えから始めます。

1 3 4 8 15 16 20
 2 1 4 7  1  4      differences,  a[i+1] - a[i]

ここで、20 が中央に移動し、その後右側に値が徐々に離れていく必要があります。解の 20 の左側の差は正であるため、値自体は昇順、つまりソートされています。したがって、それらのいくつかを選択して最大要素の右側に移動した後に残ったものはそのまま残り、(正の) 差は降順でなければなりません。そうであれば、解決策が見つかります。

ここには解決策はありません。可能性は次のとおりです。

...  20 16 8    (no more)  left:  1 3 4 15    (diffs: 2 1 11 5) 
...  20 16 4    (no more)  left:  1 3 8 15    (diffs: 2 5 7 5)
...  20 16 3    (no more)  left:  1 4 8 15    (diffs: 3 4 7 5)
...  20 16 1    (no more)  left:  3 4 8 15  ....................
...  20 15 8    (no more)  left:  1 3 4 16
...  20 15 4    (no more)  left:  1 3 8 16
...  20 15 3    (no more)  left:  1 4 8 16
...  20 15 1    (no more)  left:  3 4 8 16
...  20 8       (no more)  left:  1 3 4 15 16
...  20 4       (no more)  left:  1 3 8 15 16
...  20 3       (no more)  left:  1 4 8 15 16
...  20 1       (no more)  left:  3 4 8 15 16
...  20         (no more)  left:  1 3 4 8  15 16

1 と 3 がなければ、いくつかの解決策が考えられます。

于 2013-03-31T10:05:44.797 に答える
1

この問題の解決策が常に可能であるとは限りません。たとえば、X[] = {0, 0, 0}両方の差が常に等しいため、必要に応じて配列を「ソート」することはできません。

この問題に解決策がある場合、左の図に示すように配列値を「ソート」する必要があります。昇順の値の一部のサブセットが結果の配列のプレフィックスを形成し、降順の残りのすべての値がそのサフィックスを形成する必要があります。 . そして、「ソートされた」配列は凸状でなければなりません。

ここに画像の説明を入力

これはアルゴリズムのヒントになります。配列をソートし、その値を 2 つの凸サブセットに分割し、これらのサブセットの 1 つを抽出して最後に (逆の順序で) 追加します。

単純な (部分的な) 実装は次のようになります: 配列を並べ替え、凸包に属する値のサブセットを見つけ、残りのすべての値をチェックし、それらが凸である場合は最後に追加します。このアルゴリズムは、サブセットの 1 つが他のサブセットよりも完全に下にある場合にのみ機能します。

結果のサブセットが交差する場合 (右の図に示すように)、このアルゴリズムの改良版を使用できます: ソートされた配列を、サブセットの 1 つが他のサブセット (AB、BC) の下に完全にあるセグメントに分割し、これらのそれぞれについてセグメントは凸包を見つけ、残りのサブセットの凸性をチェックします。右側の図の X 軸は、特別な方法で配列のインデックスに対応することに注意してください。交点間の値の X 座標は、結果の配列内の位置に従ってスケーリングされます。

アルゴリズムのスケッチ

  1. 配列を昇順に並べ替えます。
  2. 最大値から始めて、「トップ」サブセットに凸包値を追加してみてください (グラハム スキャン アルゴリズムと同様の方法で)。また、凸包に属さないすべての値を「下」サブセットに入れ、その凸性をチェックします。すべての値が「上位」または「下位」のサブセットに適切に収まるまで続行します。最小値が処理されたら、これらのサブセットの 1 つを配列から削除し、サブセットを逆にして、配列の and に追加します。
  3. 「上部」サブセットに何らかの値を追加した後、「下部」サブセットが凸状でなくなった場合は、最後の追加をロールバックして、この値を「下部」サブセットに適切に追加できるかどうかを確認します。そうでない場合は、必要に応じて入力配列を「並べ替える」ことができないため、停止します。それ以外の場合は、「上位」と「下位」のサブセットを交換し、手順 2 に進みます (既に処理された値をサブセット間で移動しないでください。それらを移動しようとすると、手順 3 に進みます)。

言い換えれば、ソートされた配列の各値を最大から最小まで処理し、この値を 2 つのサブセットのいずれかに追加して、両方のサブセットが凸状のままになるようにすることができます。最初に、以前の値が追加されたサブセットに新しい値を配置しようとします。これにより、以前に追加されたいくつかの値がこのサブセットに適合しなくなる可能性があります。次に、それらがすべて他のサブセットに適合するかどうかを確認します。そうである場合は、それらを他のサブセットに移動し、そうでない場合は、それらを「トップ」サブセットのままにして、現在の値を他のサブセットに移動します。

時間の複雑さ

各値は、「最上位」サブセットに最大 1 回追加または削除されます。また、「最下位」サブセットに追加されるのは最大 1 回です。そして、要素の操作ごとに、最も近い先行操作を 2 つだけ検査する必要があります。これは、ステップ 2 と 3 の最悪の場合の時間計算量が O(N) であることを意味します。したがって、全体的な時間の複雑さは、ステップ 1 の並べ替えアルゴリズムによって決定されます。

于 2013-03-31T13:43:05.140 に答える