3 янв. 2013 г.

Задачка: Перестановки в массиве

Дан массив
[ a1, a2, ... an, b1, b2, ... bn ]

Необходимо переставить элементы в массиве, так, чтобы получился

[ a1, b1, a2, b2, ... an, bn ]

замечание: дополнительная память O(1), сложность < O(n2)

5 комментариев:

Yury комментирует...

Вот такое решение получилось
https://github.com/Falland/Reordering

Vladimir Dolzhenko комментирует...

сложность ~ (n^2) / 2 перестановок, т.е O(n^2)

Andrey комментирует...

Пусть arraycopy - атомарная операция, тогда:
static void shift(int[] array) {
int k = 1;
int p = array.length / 2;
while (k < p) {
int temp = array[p];
System.arraycopy(array, k, array, k + 1, p - k);
array[k] = temp;
k += 2;
p++;
}
}

Denis Bazhenov комментирует...

Формально это задача транспозиции матрицы. Для транспозиции есть линейные алгоритмы – http://www.cse.nd.edu/~shu/research/papers/ipdps01.pdf

xonix комментирует...

Вроде N ln N получилось.

http://ideone.com/I9gTTk