インタビュー質問：メモリ内の2つの配列の場所を置換する

Question

2つの連続した配列AとBが与えられています。彼らはあなたがBがAの前に現れるように、アレイのメモリ内AとBの順序を切り替えるうプログラムを記述する必要が

int AandB[] = {a1,a2,...,am,b1,b2,...,bn}; 

のようなものを見て。この例では、AandBは

int AandB[] = {b1,b2,...,bn,a1,...,am}; 

なるべきことを行うための最も効率的な方法は何ですか？

Answer 1

三アレイが反転：（明確にするために省略タイプ、等）REVについて

rev(AandB, 0, n+m) 
rev(AandB, 0, m) 
rev(AandB, m, n) 

：

(a1 a2 a3 a4 a5 b1 b2 b3) 
b3 b2 b1 a5 a4 a3 a2 a1 
(b3 b2 b1)a5 a4 a3 a2 a1 
b1 b2 b3 a5 a4 a3 a2 a1 
b1 b2 b3(a5 a4 a3 a2 a1) 
b1 b2 b3 a1 a2 a3 a4 a5 

は、開始と終了をとり "REV" 機能を使用して表現しました

rev(x, i, j) { 
    j--; // j points to one after the subarray we're reversing 
    while (i < j) { 
     tmp = x[i]; 
     x[i] = x[j]; 
     x[j] = tmp; 
     i++; 
     j--; 
    } 
} 

Answer 2

私たちはPHPのarray_mergeを使用できます。

array_splice()を使用して最初にこれらの配列を分割し、上記の関数を使用します。これはPHP用です。

Answer 3

私の答え：

まず、私はm<nことWLOGと仮定しています。

すべての置換は独立したサイクルに分解することができるので、a1,...,am,b1,..,bnからb1,..,bn,a1,...,amまでの置換を行うことができます。そして、インデックスiが与えられてから、p(i)を計算するのは簡単です（wlogがm<nなら、i<=mならp(i)=n+i、i>mならp(i)=i-m）。

我々はAandB[i]で始まり、p(i)=jにその値を移動し、その後、AandB[j]の値を取り、順列がばらばらサイクルに分解することができますのでp(j)などに移動することができ、我々はiに終わるだろう。

すでに移動した要素を把握するだけで済みます。私たちのケースでは、置換のサイクルにはAという2つの連続する要素が含まれないことを証明することができるので、Aの要素数を追跡するだけで十分だと思います。

として効率的ではない別の簡単なオプションは、 は{a1,...,am,b1,...bn}与えられ、{b(n-m)...b(n),b(1)..b(m),a1..am}を取得し、b(n-m)..b(n)でa1..amを交換することが可能であることに注意することです。そして、再帰によって、配列の最初のn要素について同じ問題を解決してください。しかし、これはおそらく効率的ではありません。

私が省略した詳細はいくつかありますが、いずれにせよインタビュアーはそれが行く方法ではないと言いました。非常に簡単なソリューションもあります。

Answer 4

あなたがしたい変換は、基本的に循環シフトであるn（またはシフトの方向によってはm）です。

例えば、我々は、この変換中に（私は2つのアレイを分離する文字と数字を使用） 1 2 3 4 5 6 7 a b cを有する1は4の位置に移動し、4は、7にcから7を移動し、3からc、3に6など最終的には、開始位置の1に戻ります。
そのときに1つの番号を移動して、完了しました。

変換を完了する前に1に戻る場合があります。 1 2 a b c dの場合と同様に、位置は1 -> a -> c -> 1になります。この場合は、2から始まり、操作を繰り返す必要があります。

私たちが必要とする反復量は、nとmの最大公約数です。

ので、コードが簡単にwell-known recursive formulaとO(logn)で計算することができ

int repetitions = GCD(n, m); 
int size = n + m; 
for (int i = 0; i < repetitions; ++i) { 
    int current_number = a[i]; 

    int j = i; 
    do { 
     j = (j + n) % size; 

     int tmp = current_number; 
     current_number = a[j]; 
     a[j] = tmp; 
    } while (j != i); 
} 

最大公約数のようになります。

編集
それは仕事をし、私はJavaでみました。私は表現を簡単にするためにデータ型を文字列に変更しました。

String[] a = {"1", "2", "3", "4", "5", "6", "a", "b", "c"}; 
    int n = 3; 
    int m = 6; 

    // code from above... 

    System.out.println(Arrays.toString(a)); 

そして、ユークリッドの式：私はあなたが一つ以上を作成することでごまかすことができない「メモリ内」で想定してい

int GCD(int a, int b) { 
    if (a == 0) { 
     return b; 
    } 
    return GCD(b % a, a); 
} 

Answer 5

さて、ここでの入力中に考えて...

新しい配列、たとえ一時的なものであっても。また、はに1つの一時変数を持つと仮定します（それ以外の場合は、コンテンツのスワッピングは非常に難しくなります）。

それはあなただけで

だからあなたはどこ「」アレイを把握する必要がありなど、B1とB2とA2とA1交換することはできませんので、異なるサイズすることができ、あなたの2つのサブアレイのように見えます要素が最初に開始されます。あなたは "n"を見つけることによってそれを行います。次に、最初の残りの "a"要素を繰り返し保存し、残りの最初の "b"要素をそこに配置する必要があります。

ここでそれは難しいです。保存する "a"要素を正当な場所に置く必要がありますが、スワップされていない要素が含まれている可能性があります。一番簡単なやり方は、残りの要素をすべて1つ上にシフトし、最後に保存した「a」を置くことです。これを繰り返し行うと、すべてが適切な場所に配置されます。配列が大きければそれはずいぶんシフトしています。

私は、delta領域（最初の "q" elelments、ここで "q"は配列サイズの間のデルタです）とデルタ領域で作業している間だけ、deltaの要素のシフトを行うことができると思います。その後は単純なスワップに過ぎません。