Это сделает это. Результат отличается от предложенного результата, но равен приведенным правилам (текст задачи не включает слово «сортировка», только то, что в конце вы должны переместить все 0, которые вы можете сделать даже позиции и 1 вы можете в нечетных позициях. Вам не нужно их "сжимать"). Это немного сложнее сделать это "сжатие".
static void Main(string[] args)
{
var input = new[] { 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1 };
var lastEvenToMove = -1;
var lastOddToMove = -1;
for (int i = 0; i < input.Length; i++)
{
bool needEven = i % 2 == 0;
bool isEven = input[i] == 0;
if (needEven == isEven)
{
continue;
}
if (needEven)
{
if (lastEvenToMove != -1)
{
var old = input[lastEvenToMove];
input[lastEvenToMove] = 1;
input[i] = 0;
lastEvenToMove = old;
}
else
{
input[i] = lastOddToMove;
lastOddToMove = i;
}
}
else
{
if (lastOddToMove != -1)
{
var old = input[lastOddToMove];
input[lastOddToMove] = 0;
input[i] = 1;
lastOddToMove = old;
}
else
{
input[i] = lastEvenToMove;
lastEvenToMove = i;
}
}
}
while (lastEvenToMove != -1)
{
var old = input[lastEvenToMove];
input[lastEvenToMove] = 0;
lastEvenToMove = old;
}
while (lastOddToMove != -1)
{
var old = input[lastOddToMove];
input[lastOddToMove] = 1;
lastOddToMove = old;
}
Console.WriteLine(@"{{{0}}}", String.Join(", ", input.Select(p => p.ToString())));
}
Я храню стопку шансов и стопку четных элементов, которые нужно переместить, и использую их, когда мне нужно нечетное / четное число. Два стека хранятся во входном массиве, поэтому нет дополнительного пространства (кроме двух «головок» двух стеков, которые представляют собой два дополнительных целых числа). Я думаю, что наихудший случай - O(1.5n) для времени (например, все элементы 1, половина элементов «помещена» в стек и затем нуждается в сбросе, потому что не было пустого места), и O(1) для космоса.
Выход:
{0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1}