▼

3 янв. 2013 г.

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

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

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

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

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

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

  1. Yury03 января, 2013 23:23

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

    ОтветитьУдалить
  2. Vladimir Dolzhenko03 января, 2013 23:45

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

    ОтветитьУдалить
  3. Andrey04 января, 2013 03:04

    Пусть 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++;
    }
    }

    ОтветитьУдалить
  4. Denis Bazhenov12 января, 2013 09:20

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

    ОтветитьУдалить
  5. xonix03 февраля, 2013 03:27

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

    http://ideone.com/I9gTTk

    ОтветитьУдалить