Переставить нечетные и четные числа

Существует ли алгоритм O(n) для перестановки нечетных и четных чисел с сохранением порядка? Вспомогательные массивы могут использоваться для промежуточных результатов, но перестановка должна производиться внутри массива.

Я нашел это http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/, чтобы делать то, что требуется, но не поддерживает порядок

Input:
1 4 3 8 6 5 7

Output:
1 3 5 7 4 8 6

algorithm complexity-theory divide-and-conquer
person mhn    schedule 29.02.2016    source источник
comment
ввод всегда сортируется? если это не так, то это невозможно сделать O(n)   -  person Marc B    schedule 01.03.2016
comment
Почему вы спрашиваете есть ли...? Вы знаете, что есть один? Вам это нужно?   -  person Amit    schedule 01.03.2016
comment
Произвольна ли последовательность чисел? Если да, то отразите это в своем примере, потому что то, как вы это изложили, сбивает с толку читателей.   -  person Basel Shishani    schedule 01.03.2016
comment
Да, последовательность чисел произвольная. Я хотел знать, есть ли способ сделать это в двухпроходном алгоритме или около того. Поскольку общая сложность по-прежнему будет O (n). Вспомогательные массивы могут использоваться для промежуточных результатов, но перестановка должна выполняться внутри массива.   -  person mhn    schedule 01.03.2016

Ответы (1)


arrow_upward
1
arrow_downward

Как насчет этого?

  1. Создайте два двусвязных списка (или что-то, что имеет конкатенацию O (1)), чтобы хранить нечетные и четные числа отдельно.
  2. Переберите входной список, разделите их на списки на шаге 1.
  3. Объединить два списка.
person utdemir    schedule 29.02.2016
comment
Ваш третий шаг должен заполнить массив из содержимого списков. Но с действительно связанными списками сложно работать, если вам не нужно... - person Amit; 01.03.2016
comment
@Amit, я думаю, это зависит от; Я считаю, что связанные структуры данных легче рассуждать. Это также зависит от языка программирования, чисто функциональный язык, такой как Haskell, может предпочесть связанные списки вместо массивов. - person utdemir; 01.03.2016
comment
Я предположил, что вопрос касается массивов (ввод и вывод), но на самом деле об этом ничего не говорится. Он говорит (теперь, после редактирования) нет вспомогательного массива, так что я думаю, это означает, что ваш ответ тоже недействителен. Однако со связанными списками вам не нужны никакие вспомогательные конструкции, просто перемещайте элементы в нужное место. Это O(n). - person Amit; 01.03.2016
comment
@Amit, верно, если для вопроса требуются массивы, мой ответ требует дополнительной памяти O (n) вместо O (1) со связанными списками. Но это все еще сложность времени O (n). - person utdemir; 01.03.2016