Движение массива от a1,.., an, b1,.., bn до a1, b1,..., an, bn

Сегодня я встретил вопрос, который действительно озадачил меня.

Вопрос

У меня есть массив, как: arr[a1, a2, a3....an, b1, b2, b3.....bn], как перемещать элементы массива, чтобы передать его в arr[a1, b1, a2, b2......an,bn], и вы должны сделать движение на месте (space complexity should be constant).

Я попытался изо всех сил подумать об этом и получить уродливый алгоритм, подобный пузырь-сортировке:

b1 moves forward by n - 1;
b2 moves forward by n - 2;
.
.
bn-1 moves forward by 1;

Но временная сложность O (n 2), кто может дать мне лучший алгоритм? Я нахожу еще один лучший метод, например quick-Sort:

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)

здесь представлены целые коды:

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);
}

Ответы

Ответ 1

После того, как я немного размышлял и экспериментировал/спотыкался, я думаю, что начинаю понимать, хотя математика по-прежнему тяжела для меня. Я думаю, что это происходит примерно так:

Определите циклы перестановки транспозиции (это можно сделать во время или до фактической передачи данных). Формулу to = 2*from mod (M*N - 1), where M = 2, N = array length / 2 можно использовать для поиска указателей (перестановки) индекса. (Я уменьшил формулу для этого вопроса, так как мы знаем M = 2.) Маркер посещаемых индексов может помочь определить начало следующего цикла (технически говоря, можно использовать вычисления циклов, а не битов в качестве маркера, сохраняя только следующий цикл - начало в памяти). Временная переменная хранит данные с начального адреса до конца цикла.

В целом это может означать две временные переменные, вычисления циклов и одно перемещение на месте для элемента массива.

Например:

arr          = 0,1,2,3,4,5,6,7,8,9
destinations:  0,2,4,6,8,1,3,5,7,9

start = 1, tmp = arr[1]    

cycle start
5->1, 7->5, 8->7, 4->8, 2->4, tmp->2
cycle end

not visited - 3

start = 3, tmp = arr[3]

cycle start
6->3, tmp->6
cycle end

Transposition complete.

Есть вопросы?
Не стесняйтесь спрашивать и пожалуйста, посетите http://en.wikipedia.org/wiki/In-place_matrix_transposition

Ответ 2

Вот короткий код в Python, который делает это:

n = 4
a = ['a1', 'a2', 'a3', 'a4', 'b1', 'b2', 'b3', 'b4']
result = a[:n]
for index in range(n):
    result.insert(index*2 + 1, a[n+index])
print result  #  prints ['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'b4']

Ответ 3

Возможно, это не лучший способ, потому что он не отвечает на ваш вопрос напрямую, но почему бы вам просто не просто сопоставить новые индексы элементов со старыми индексами элементов?

old_array: [a1, a2, a3....an, b1, b2, b3.....bn]
=>
lookup: [0 n 1 n+1 2 n+2 ... n-1 2n-1]
=>
[a1 b1 a2 b2 ... an bn]

Если вы хотите захватить элемент из индекса

Get(index)
 return old_array[lookup[index]]
End

Get(2) => old_array[lookup[2]] => old_array[1] => a2 | a2 is at index 2

Ответ 4

Рабочий Java-код для "Движения массива от a1,.., an, b1,.., bn до a1, b1,.., an, bn" 

private static void myTrans(int[] m) {
    int n = (m.length - 1);

    int i = 1;
    for (int start = 1; start < n; start++) {
        int temp = m[start];
        m[start] = m[n / 2 + i];

        for (int j = (n / 2 + i); j > start; j--) {
            m[j] = m[j - 1];
        }

        start++;
        m[start] = temp;
        printArray(m);
        i++;
    }
}

Ответ 5

public void shuffle(char[] arr, int left, int right){
    //center
    int c = (left+right)/2;
    int q = 1 + (left+c)/2;
    for(int k=1,i=q;i<=c;i++,k++){
         //Swap elements
         int temp = arr[i];
         arr[i] = arr[c+k];
         arr[c+k] = temp;
    }
    shuffle(arr,left,c);
    shuffle(arr,c+1,right);
}

Это будет перемешаться по центру:

  • a1a2a3a4b1b2b3b4 → a1a2b1b2a3a4b3b4
  • a1a2b1b2 → a1b1a2b2
  • a3a4b3b4 → a3b3a4b4

Сложность этого решения будет nlogn

Ответ 6

Предположим, что входной массив задан как [a1, a2, a3, b1, b2, b3, c1, c2, c3], так что в соответствии с вопросом мы хотим, чтобы результат как [a1, b1, c1, a2, b2, c2, a3, b3, c3]. Позвольте мне представить массив как двумерную матрицу с каждой строкой, обозначающей размер группы n (n в этом случае 3).

Original array
a1 a2 a3
b1 b2 b3
c1 c2 c3

What we Want
a1 b1 c1
a2 b2 c2
a3 b3 c3

Вы заметили что-то. Позвольте мне сказать, что выходной массив на самом деле транспонировать входного массива, представленного как 2D-матрица, который можно легко сделать с использованием постоянного пространства.

  • Примечание. Вам необходимо разработать свою логику для разбиения этого исходного массива на 2D-массив.

Внедрение Код