Массив чередования в постоянном пространстве

Это последовательность и заметки, которые я написал ручкой и бумагой . Я думаю, что это или вариант будет справедлив для любого большего n.

Каждая линия представляет отдельный шаг, и () означает, что перемещается на этом шаге, а [] - это то, что было перемещено с последнего шага. Сам массив используется в качестве хранилища, и два указателя (один для L и один для N) необходимы, чтобы определить, что двигаться дальше. L означает «буквенная строка», а N - «числовая строка» (то, что перемещается).

  A  B  C  D   1  2  3  4

L A  B  C (D)  1  2  3  4 first is L, no need to move last N
N A  B  C (3)  1  2 [D] 4
L A  B (C) 2   1 [3] D  4
N A  B  1 (2) [C] 3  D  4
L A (B) 1 [2]  C  3  D  4
N A (1)[B] 2   C  3  D  4
  A [1] B  2   C  3  D  4 done, no need to move A

Обратите внимание на различные «скачки указателя» - указатель L всегда уменьшается на 1 (так как он не может быть поглощен быстрее, чем это), но указатель N перескакивает в зависимости от того, "заменил ли он себя" (на месте, прыгните на два вниз) или если он что-то поменял (никакого перехода, чтобы следующее что-то могло начать свое дело!)

YMMV

Если вы можете сначала преобразовать массив в связанный список, проблема станет тривиальной.

Во-первых, теория: перегруппируйте элементы в «циклах перестановок». Возьмите элемент и поместите его на новое место, сместив элемент, который там сейчас находится. Затем вы берете этот смещенный элемент и помещаете его в новое положение. Это вытесняет еще один элемент, поэтому промойте и повторите. Если смещенный элемент принадлежит позиции элемента, с которого вы впервые начали, вы завершили один цикл.

На самом деле, ваш - частный случай вопроса, который я задал здесь , а именно: Как сделать вы переставляете массив в любой заданный порядок за время O (N) и пространство O (1)? В моем вопросе переставленные позиции описываются массивом чисел, где число в n-й позиции указывает индекс элемента в исходном массиве.

Однако вы этого не делаете. У вас есть этот дополнительный массив в вашей проблеме, и его выделение займет O (N) пространства. К счастью, мы можем вычислить значение любого элемента в этом массиве на лету, например:

int rearrange_pos(int x) {
    if (x % 2 == 0) return x / 2;
    else return (x - 1) / 2 + n; // where n is half the size of the total array
}

Я не буду здесь дублировать сам алгоритм перестановки; его можно найти в принятом ответе на мой вопрос.

Изменить: Как указал Джейсон, ответ, с которым я связался, по-прежнему требует выделения массива bools, что делает его пространством O (N). Это потому, что перестановка может состоять из нескольких циклов. Я пытался исключить необходимость в этом массиве для вашего особого случая, но безуспешно ... Похоже, что нет подходящего шаблона. Может быть, здесь кто-нибудь еще сможет вам помочь.

t продублируйте здесь сам алгоритм перестановки; его можно найти в принятом ответе на мой вопрос.

Изменить: Как указал Джейсон, ответ, с которым я связался, по-прежнему требует выделения массива bools, что делает его пространством O (N). Это потому, что перестановка может состоять из нескольких циклов. Я пытался исключить необходимость в этом массиве для вашего особого случая, но безуспешно ... Похоже, что нет подходящего шаблона. Может быть, здесь кто-нибудь еще сможет вам помочь.

t продублируйте здесь сам алгоритм перестановки; его можно найти в принятом ответе на мой вопрос.

Изменить: Как указал Джейсон, ответ, с которым я связался, по-прежнему требует выделения массива bools, что делает его пространством O (N). Это потому, что перестановка может состоять из нескольких циклов. Я пытался исключить необходимость в этом массиве для вашего особого случая, но безуспешно ... Похоже, что нет подходящего шаблона. Может быть, здесь кто-нибудь еще сможет вам помочь.

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

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

Эта проблема не такая тривиальная, как и люди. Домашнее задание? РЖУ НЕ МОГУ.

Следующая ссылка имеет решение: http://arxiv.org/abs/0805.1598

Эта проблема не так проста, как кажется, но после некоторого размышления алгоритм для ее решения не так уж и плох. Вы заметите, что первый и последний элементы уже на месте, поэтому нам не нужно о них беспокоиться. Мы сохраним левую индексную переменную, которая представляет первый элемент в первой половине массива, который необходимо изменить. После этого мы устанавливаем правую индексную переменную для первого элемента во второй половине массива, который необходимо изменить. Теперь все, что мы делаем, это меняем местами элемент в правом индексе один за другим вниз, пока он не достигнет элемента левого индекса. Увеличьте левый индекс на 2 и правый индекс на 1 и повторяйте до тех пор, пока индексы не совпадут или левый не пройдет за правый индекс (правый индекс всегда будет заканчиваться на последнем индексе массива). Мы увеличиваем левый индекс на два каждый раз, потому что элемент слева + 1 уже естественным образом встал на свое место.

Псевдокод

1. Установить левый индекс на 1
2. Установить правый индекс в середину (длина массива / 2)
3. Поменять местами элемент в правом индексе на элемент, непосредственно предшествующий ему, пока он не заменит элемент в left index
4. Увеличить левый индекс на 2
5. Увеличить правый индекс на 1
6. Повторить 3–5, пока левый индекс не станет больше или равен правому индексу

Алгоритм чередования в C (#)

protected void Interleave(int[] arr)  
{  
    int left = 1;  
    int right = arr.Length / 2;  
    int temp;  

    while (left < right)  
    {  
        for (int i = right; i > left; i--)  
        {  
            temp = arr[i];  
            arr[i] = arr[i - 1];  
            arr[i - 1] = temp;  
        }  

        left += 2;  
        right += 1;  
    }  
}    

В этом алгоритме используется память O (1) (с временной переменной, которую можно исключить с помощью метода обмена сложением / вычитанием). Я не очень хорошо разбираюсь в анализе времени выполнения, но я считаю, что это все еще O (n), даже хотя мы делаем много свопов. Возможно, кто-нибудь сможет дополнительно изучить его анализ времени выполнения.