13

配列 S を入力として受け取り、S を 3 つのセット (負、ゼロ、および正) に分割する O(n) アルゴリズムを指定します。これをその場で、つまり新しいメモリを割り当てずに実装する方法を示します。また、番号の相対的な順序を維持する必要があります。例: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

そのような解決策が存在するかどうかはわかりません。私が考えることができる最善の解決策は次のとおりです。

解決策 1: 追加の整数配列を使用して、配列全体をトラバースして、負の値、0、正の値の順に取得します。

解決策 2: 数値の相対順序を保持しない。次に、配列を 2 回ループします。

    template <typename Type>  
void Partion(Type *array, int begin, int end, Type v, int &l, int &r) 
{  
    l = begin;  
    for (int i=begin; i!=end; ++i)  
    {  
        if (array[i] < v)  
            swap(array[i], array[l++]);  
    }  
    r = l;  
    for (int j=l; j!=end; ++j)  
    {  
        if (array[j] == v)  
            swap(array[j], array[r++]);  
    }  
}
4

5 に答える 5

3

これが役立つかどうかはわかりませんが、安定して 3 つのクラスに分割する必要があることは、安定して 2 つのクラスに分割するという問題に還元できます。負のものを非負のものから分離し、次に正のものを非正のものから分離します。2 クラスの問題が O(1) 空間と O(n) 時間で解ける場合、その解を 2 回適用して元の問題を解くことができます。

于 2011-03-18T07:55:52.800 に答える
1

ゼロは見分けがつかないので、それらが交換されたり、最後に単に上書きされたりしても気にしないと思います（つまり、正と負の数値を配列の反対側に移動した後、中央部分をゼロにします）。

整数がより大きなものの単なるキーである状況を見ている場合、これは当てはまらない可能性があります-ゼロを保持し、安定して分割する必要がある場合があります。しかし、そうでない場合は、次の 2 つの洞察があります。

まず、あなたの問題は、安定したバイナリ パーティションの問題と同じです。

もちろん、問題のアルゴリズムは、安定したバイナリパーティション（ゼロのない配列のみ）を行います。逆に、配列にゼロがある場合でも、バイナリ パーティションを使用して汚れた作業を行うことができます: 配列全体をスキャンし、遭遇した各ゼロを次の負の値と交換します (それがどこにあったかを追跡するので、実行しません)。 n^2 全体のスキャン)、結果として

[混合 -,+][おそらく余分なゼロ][混合 0,+].

次に、取得するために 2 つのバイナリ パーティションを実行します。

[-][+][0][+]

+ 値をシフトして、目的の結果を取得します。

私の知る限り、バイナリパーティションでは、安定、インプレース、および O(n) のいずれか 2 つを選択できます。運が悪いように見えますが、どうやらインプレース O(n*log n) アルゴリズムは、log(n) スクラッチ スペースを使用する O(n) アルゴリズムとして知られています。

第 2 に、ゼロの数が少なくとも f(n) であることを保証できる場合、ゼロはスクラッチ スペースの不足を補うことができます。時間 O(n^2/f(n)) で安定したインプレース パーティションを取得するのは簡単です。特に、ゼロが配列の少なくとも一部の一定の割合になる場合は、完了するまで次の 2 つの手順を実行するだけで O(n) ランタイムが得られます。

  1. 配列全体をスキャンし、遭遇した各ゼロを次の負の値と交換します
  2. 配列を左にスキャンし、遭遇した各ゼロを次の正の値と交換します

ゼロが他のタイプのいずれかと同じくらい多い場合、これは 1、2、1 の順に実行した後に行われます。

于 2011-08-31T06:42:00.447 に答える
0

C ++ライブラリには、インプレースで実行するときにn回の比較とO（n log n）スワップstable_partitionを必要とするアルゴリズムがあります。

@Tedが指摘しているように、この問題にはこのアルゴリズムの2つのアプリケーションが必要です。

于 2011-03-18T11:38:29.500 に答える
0

これは、符号のみをチェックするカスタムコンパレータで実行される「安定ソート」を使用して単純に行うことはできませんか？

編集：
いいえ、それはO（n log n）です。

線形時間で実行できることの1つは、問題を減らすことです。ゼロは順序付けできないため（どのように区別しますか？）、ゼロをスキップしてゼロ以外の値を入力しながら、配列をウォークスルーするパスを作成できます。次に、最後に正しい数のゼロを追加します。

j=0;
for (i=0;i<N;i++) {
  if (A[i]) {
     A[j++]=A[i];
  }
}
while (j<N) {
   A[j++]=0;
}

これで最後のセクションを無視でき、問題は0付近の安定したパーティションのO（n）アルゴリズムを見つけることになります。残念ながら、c ++ stlstable_partitionの関数にはO（n）の比較しかありませんが、O（n log n）は次の場合にスワップします。追加のスペースはありません。

ただし、この記事：「線形時間での安定した最小スペース分割」は、O（n）で可能であることを示しているようです。ここで明確に要約するのに十分理解していないと思います。

それが機能する場合、最後のステップは、パーティションの間にゼロを挿入することです。これもO（n）です。これは、ゼロには維持する順序がないためです。

于 2011-03-18T03:24:39.687 に答える