Дан массив
[ a1, a2, ... an, b1, b2, ... bn ]
Необходимо переставить элементы в массиве, так, чтобы получился
[ a1, b1, a2, b2, ... an, bn ]
замечание: дополнительная память O(1), сложность < O(n2)
[ a1, a2, ... an, b1, b2, ... bn ]
Необходимо переставить элементы в массиве, так, чтобы получился
[ a1, b1, a2, b2, ... an, bn ]
замечание: дополнительная память O(1), сложность < O(n2)
5 комментариев:
Вот такое решение получилось
https://github.com/Falland/Reordering
сложность ~ (n^2) / 2 перестановок, т.е O(n^2)
Пусть 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++;
}
}
Формально это задача транспозиции матрицы. Для транспозиции есть линейные алгоритмы – http://www.cse.nd.edu/~shu/research/papers/ipdps01.pdf
Вроде N ln N получилось.
http://ideone.com/I9gTTk
Отправить комментарий