15

今日、私は本当に困惑している質問に出会いました

質問

私は のような配列を持っています: arr[a1, a2, a3....an, b1, b2, b3.....bn], 配列の要素を移動して に転送する方法arr[a1, b1, a2, b2......an,bn], そして移動はその場で行う必要があります.

私はそれをよく考えてみて、バブルソートのような醜いアルゴリズムを得るために最善を尽くしました:

b1 moves forward by n - 1;
b2 moves forward by n - 2;
.
.
bn-1 moves forward by 1;

しかし、時間計算量は O(n 2 ) です。より良いアルゴリズムを教えてくれる人はいますか? クイックソートと同じように、別のより良い方法を見つけました。

First we swap the element from a(n/2) to a(n) with the elements from b1 to b(n/2);now we get two independent sub problems,So we can solve it by recursion.
T(n) = 2T(n/2) + O(n) 
the time complexity is O(nlgn)

ここにコード全体があります：

void swapArray(int *arr, int left, int right)
{
    int mid = (left + right) >> 1;
    int temp = mid + 1;
    while(left <= mid)
    {
        swap(arr[left++], arr[temp++]);
    }
}
void arrayMove(int *arr, int lb, int le, int rb, int re)
{
    if(le - lb <= 0 || re - rb <= 0)
        return;
    int mid = (lb + le + 1) >> 1;
    int len = le - mid;
    if(rb + len >= re)
    {
        swapArray(arr, mid + 1, rb);
    }
    else
    {
        swapArray(arr, mid, rb + len);
    }
    arrayMove(arr, lb, mid - 1, mid, le);
    arrayMove(arr, rb, rb + len, rb + 1 + len, re);
}
4

7 に答える 7

2

少し手を出して実験/つまずいた後、数学はまだ難しいですが、理解し始めていると思います. 次のようになると思います。

転置の順列サイクルを決定します (これは、実際のデータ転送中または前に行うことができます)。式 をto = 2*from mod (M*N - 1), where M = 2, N = array length / 2使用して、インデックスの宛先を見つけることができます (順列)。(M = 2 であることがわかっているので、この質問の式を減らしました。) 訪問したインデックスのマーカーは、次のサイクルの開始を決定するのに役立ちます (技術的に言えば、マーカーとしてビットセットではなくサイクル計算を使用して、メモリ内の次のサイクル開始)。一時変数は、開始アドレスからサイクル終了までデータを保持します。

全体として、これは 2 つの一時変数、サイクル計算、および配列要素ごとに 1 つのインプレース移動を意味する可能性があります。

例えば：

arr          = 0,1,2,3,4,5,6,7,8,9
destinations:  0,2,4,6,8,1,3,5,7,9

start = 1, tmp = arr[1]    

cycle start
5->1, 7->5, 8->7, 4->8, 2->4, tmp->2
cycle end

not visited - 3

start = 3, tmp = arr[3]

cycle start
6->3, tmp->6
cycle end

Transposition complete.

質問は？
お気軽にお問い合わせください。http://en.wikipedia.org/wiki/In-place_matrix_transpositionにアクセスしてください。

于 2013-08-04T20:55:54.873 に答える
0

「a1,..,an,b1,..,bn から a1,b1,..,an,bn への配列の移動」の作業 Java コード

private static void myTrans(int[] m) {
    int n = (m.length - 1);

    int i = 1;
    for (int start = 1; start < n; start++) {
        int temp = m[start];
        m[start] = m[n / 2 + i];

        for (int j = (n / 2 + i); j > start; j--) {
            m[j] = m[j - 1];
        }

        start++;
        m[start] = temp;
        printArray(m);
        i++;
    }
}
于 2014-09-06T07:48:01.173 に答える
0

これを行う Python の短いコードを次に示します。

n = 4
a = ['a1', 'a2', 'a3', 'a4', 'b1', 'b2', 'b3', 'b4']
result = a[:n]
for index in range(n):
    result.insert(index*2 + 1, a[n+index])
print result  #  prints ['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'b4']
于 2013-08-04T14:11:52.390 に答える
-2

入力配列が[a1,a2,a3,b1,b2,b3,c1,c2,c3]として与えられていると仮定すると、質問に従って出力を[a1,b1,c1,a2,b2,c2, a3、b3、c3]。配列を 2D 行列として表し、各行がグループ サイズ n (この場合は n は 3) を表すようにします。

Original array
a1 a2 a3
b1 b2 b3
c1 c2 c3

What we Want
a1 b1 c1
a2 b2 c2
a3 b3 c3

何か気づきましたか。出力配列は実際には、定数空間を使用して簡単に実行できる 2D マトリックスとして表される入力配列の転置であることをお伝えします。

  • 注: この元の配列を 2D 配列に分割するためのロジックを作成する必要があります。

実装コード

于 2013-08-04T14:53:57.867 に答える