6

重複の可能性：
マトリックスのインプレース転置

最近、技術面接に出席しました。次の質問に答えました。

私は言うように配列を持っています

testArray = {a1,a2,a3,...an,b1,b2,b3,....bn,c1,c2,c3,.....,cn}

この配列を`としてソートする必要があります

testArray = {a1,b1,c1,a2,b2,c2,a3,b3,c3,.....,an,bn,cn}

制約は、余分なメモリを使用したり、組み込み関数を使用したりしないことです。完全なコードを書く必要がありますが、それは任意の言語であり、任意のデータ構造を使用することもできます。

例えば：

Input: {1,2,3,4,5,6,7,8,9}, n = 3

Output: {1,4,7,2,5,8,3,6,9}

制約内で解決策を得ることができませんでしたが、誰かが解決策や提案を提供できますか？

4

4 に答える 4

8

これは単なる行列転置演算です。また、ウィキペディアには、インプレース行列転置の問題と解決策さえあります。

少なくともアレイを通過する必要があるため、余分なスペースは不可能ではありません。O(1)追加のメモリが可能ですが、時間の複雑さに大きなペナルティがあります。

このソリューションは、ウィキペディアのページにあるサイクルに従うアルゴリズムに基づいて構築されています。セルごとに、サイクル内でインデックスが最小のセルが見つかります。インデックスが最小のセルが現在のセルのインデックス以上（> =）の場合、チェーンスワッピングを実行します。それ以外の場合は、セルが正しくスワップされているため、セルを無視します。時間計算量の（大まかに分析された）上限は、O（（MN）2）まで高くなる可能性があります（M * Nセルを通過し、サイクルはセルの総数と同じ長さになります）。

于 2012-07-16T09:07:35.703 に答える
4

不可能

リストをトラバースするにはイテレータが必要であり、スペースを消費するため、メモリと任意の長さを余分に使用せずにこのアルゴリズムを実装することは不可能です。

交換する適切なインデックスを見つける

配列の長さが固定され、nが固定されている場合は、行列転置アルゴリズムを使用できます。そして要素yを交換するために

探しているアルゴリズムは、行列転置アルゴリズムです。したがって、すべての要素を繰り返し処理するたびに、すべての要素を正確に交換する必要があります。

http://en.wikipedia.org/wiki/Transpose

基本的に、 n番目のコンポーネントのm番目の要素をm番目のコンポーネントのn番目の要素と交換する必要があります。これは、ダブルループで実行できます。

m = length(array)/n;
for (i = 0; i < m; i++)
  for (j = 0; j < n;  j++)
  {
     index_1 = i * m + j;
     index_2 = j * m + i
     swap(index_1, index_2);
  }

注：固定のmとnの場合、このループは完全に展開できるため、m、i、jは定数に置き換えることができます。

メモリを消費せずにスワッピング

余分なスペースを使用せずにすべての要素を交換するために、コメントで指摘されているようにXOR交換アルゴリズムを使用できます。

X := X XOR Y
Y := Y XOR X
X := X XOR Y
于 2012-07-16T09:49:04.087 に答える
1

一時変数を使用せずに2つの数値（aとb）を交換する最も簡単な方法は、次のとおりです。

  b = b + a;
  a = b - a;
  b = b - a;

あなたがそれを関数で書くなら、あなたはそこへの道の一部です。一時変数を使用せずに配列内でスワップする変数を追跡する方法は、今のところわかりません。

有権者のことを忘れないでください。彼は実際に配列を並べ替える必要はなく、正しい値を交換するだけです。

編集：これは、Java（およびC / C ++では、非常に積極的なコンパイラ最適化をオンにしない限り、動作は未定義ですが、デフォルトは正常です）で大きな値で機能します。値はラップアラウンドします。

2番目の編集-配列を反転させるためのいくつかの（テストされていない）コード。4つの整数がメモリ制限を超えていると思います。技術的にはスレッドセーフではありませんが、各配列の場所にアクセスするのは最大で1回だけなので、並列化できます。

static int[] a = {1,2,3,4,
                  5,6,7,8,
                  9,10,11,12,
                  13,14,15,16};

static int n = 4;

public static void main(String[] args) 
{
    for(int i = 0; i < a.length/n; i++)     //  1 integer
        for(int j = 0; j < n; j++)          //  1 integer
            if(j > i)
                swap(i*n+j, j*n+i);
}

static void swap(int aPos, int bPos)        //  2 integers
{
    if(a[aPos] != a[bPos])
    {
        a[bPos] = a[aPos] + a[bPos];
        a[aPos] = a[bPos] - a[aPos];
        a[bPos] = a[bPos] - a[aPos];
    }
}

これが質問を誤解している場合はお詫びします。私はそれを注意深く読み、これ以外に何が必要かを理解することができませんでした。

于 2012-07-16T09:19:59.017 に答える
-1

クイックソートアルゴリズムを見てください

使用可能なアルゴリズムの詳細については、アルゴリズムの並べ替えページにアクセスしてください。

于 2012-07-16T09:06:58.217 に答える