14

制約 :

  1. O(1) スペース
  2. 定刻

これは宿題の質問ではなく、私が出会った興味深い質問です。

ここに私が考えることができるいくつかの解決策がありますが、与えられた制約でそれを行うものは何もありません.

方法 1

*O(n)メモリ付き*

  • 配列を再帰的に 2 つの部分に分割します。(各サブ問題のサイズが 2 以下になるまで分割を続けます)
  • 配列を最初に、番号を最後に各サブ問題を並べ替えます。
  • サブ問題配列をマージします

方法 2

O(n log n) 時間で

  • 1234abcdになる辞書式順序に基づいて配列をソートします
  • 配列 4321dcba の両方の半分を逆にします。
  • 文字列全体を反転 abcd1234

方法 3

数値の範囲が定義されている場合

また、数値が特定の範囲内にある場合は、int say track= 0; を初期化できます。そして、配列内の数値に出くわしたときに適切なビットを設定します (例: (1 << a[2] ) 。1. アルファベットを配列の前半に入れ替えます。 2. トラック変数に数字をマークします。 3. 後で track を使用して配列の後半を埋めます。

方法 4 整数の範囲の制約を削除したい場合は、HashMap で方法 3 を使用できますが、より多くのメモリが必要になります。

O(1) 時間と O(n) 空間で一般的な問題を解決するより良い方法は考えられません。

ここでの一般的な問題とは、次のことを指します。

シーケンス x1y1x2y2x3y3....xnyn が与えられ、ここで x1 、 x2 はアルファベット x1 < x2 <.... < xn および y1y2...yn は integer です。y1 < y2 <.... < yn 出力を x1x2...xny1y2...yn として配置します

助言がありますか ？

4

4 に答える 4

6

とはn? nそれが入力のサイズであると仮定します。

これは、リストの畳み込みと呼ばれます。(a,1),(b,2),(c,3),(d,4)本質的に、ペアのリストをリストのペアに変換する必要があります(a,b,c,d),(1,2,3,4)。行列の転置と同じ操作です。

とにかく、構造を k 次元配列 (k = lg n) と考える必要があります。配列の畳み込みは、インデックス i の値をビットごとに回転したインデックス i に「移動」したときに得られるものです。この場合、インデックスを右に 1 ビット回転させます。これは、畳み込みが最大サイクル長 k の順列であることを意味します。秘訣は、各サイクルから 1 つのインデックスを選択することです。これには常に 0 と n-1 が含まれます。

EDIT：実際には、おそらくあなたが望むのは、順列を転置の製品に分解することです。次に、あなたがする必要があるのはスワップだけです。

于 2012-10-02T02:52:01.710 に答える
-3

これがO(n)の私のアルゴリズムです。

void cycle_leader(int *arr, int n) {

for (int i = 1; i < n / 2; i+= 2)
{
    int j = i;
    int save;
    int tmp = arr[i];

    do{
        if (j & 1) //odd index element
            j = n / 2 + j / 2;
        else
            j = j / 2;

        save = arr[j];
        arr[j] = tmp;
        tmp = save;
    } while(j != i);
}

}

于 2014-05-10T03:41:49.930 に答える