Есть ли алгоритм 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
Как насчет этого?
. Ваш третий шаг должен быть «заполнить массив из содержимого списков». Но действительно связанные списки - это боль, с которой нужно работать, если вам не нужно ... – Amit
@ Приходится, я думаю, это зависит; Я считаю, что связанные структуры данных легче рассуждать. Это также зависит от языка программирования, чисто функционального языка, такого как Haskell, возможно, предпочитает связанные списки вместо массивов. – utdemir
Я предполагал, что речь идет о массивах (input & output), но на самом деле он ничего не говорит об этом. Он говорит (теперь, после редактирования) никакого вспомогательного массива, поэтому я предполагаю, что это означает, что ваш ответ также недействителен. Однако со связанными списками вам не нужны вспомогательные структуры, просто переместите предметы в нужное место. Это * O (n) *. – Amit
- вход всегда отсортирован? если это не так, тогда нет способа сделать это O (n) –
Почему вы спрашиваете «* есть ли ... *»? Вы знаете, что есть один? Вам это нужно? – Amit
Является ли последовательность чисел произвольной? Если это так, то отразите это в вашем примере, потому что, как вы выразились, это путает читателей. –