Movimiento de matriz de a1, .., an, b1, .., bn a a1, b1, .., an, bn
Hoy me encontré con una pregunta que realmente me desconcierta.
Pregunta
Tengo una matriz como:arr[a1, a2, a3....an, b1, b2, b3.....bn]
, cómo mover los elementos de la matriz para transferirlo aarr[a1, b1, a2, b2......an,bn]
, Y deberías hacer el movimiento en el lugar (space complexity should be constant
).
Hice lo mejor que pude para pensarlo y obtener un algoritmo feo como el de burbuja:
b1 moves forward by n - 1;
b2 moves forward by n - 2;
.
.
bn-1 moves forward by 1;
Pero la complejidad del tiempo es O (n2), quien me puede dar un mejor algoritmo? Encuentro otro método mejor como el de ordenación rápida:
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)
Aquí hay códigos enteros:
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);
}