Разбор задачи «Сдвиг нулей в конец»

1. Идея

Нужно перестроить массив так, чтобы:

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

Самая простая идея — пройти по массиву один раз:

• все ненулевые элементы сразу записывать в ответ;
• количество нулей просто посчитать.

После этого в конец ответа дописать столько нулей, сколько встретилось.

2. Наблюдения

Наблюдение 1

От нас не требуется сортировка или какие-то перестановки по значениям. Важно только разделить элементы на две группы:

• сначала все ненулевые;
• потом все нули.

Наблюдение 2

Порядок ненулевых элементов должен сохраниться. Значит, если мы идём слева направо и добавляем в ответ только ненулевые элементы, нужный порядок получится автоматически.

Наблюдение 3

Сами нули не различаются между собой, поэтому достаточно знать только их количество.

Например, для массива:

0 5 0 -3 7

• ненулевые элементы: 5 -3 7
• нулей: 2

Итог:

5 -3 7 0 0

3. Алгоритм

1. Считать n.
2. Считать массив из n чисел.
3. Создать пустой список result.
4. Завести переменную zeros = 0.
5. Для каждого элемента x:
   • если x == 0, увеличить zeros на 1;
   • иначе добавить x в result.
6. После прохода дописать в result zeros нулей.
7. Вывести result.

4. Почему это работает

Докажем, что алгоритм строит правильный ответ.

1. Все ненулевые элементы сохраняются

Мы просматриваем каждый элемент массива ровно один раз. Если элемент не равен 0, мы добавляем его в result. Значит, каждый ненулевой элемент попадёт в ответ.

2. Порядок ненулевых элементов не меняется

Мы идём по массиву слева направо и добавляем ненулевые элементы в result в том же порядке, в котором встречаем. Поэтому их относительный порядок сохраняется.

3. Все нули оказываются в конце

Нули мы не добавляем сразу, а только считаем. После обработки всех элементов мы дописываем в конец result ровно столько нулей, сколько было в исходном массиве. Значит, все нули окажутся после всех ненулевых элементов.

4. Длина ответа правильная

Каждый исходный элемент либо:

• является ненулевым и один раз добавляется в result,
• либо является нулём и учитывается в zeros.

Потом мы добавляем zeros нулей. Значит, общее число элементов в ответе равно n.

Следовательно, полученный массив полностью соответствует условию задачи.

5. Сложность

Мы один раз проходим по массиву и затем дописываем нули.

• Время: O(n)
• Дополнительная память: O(n)

Это хорошо укладывается в ограничения при n до 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> result;
    result.reserve(n);

    int zeros = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        if (x == 0) {
            zeros++;
        } else {
            result.push_back(x);
        }
    }

    for (int i = 0; i < zeros; i++) {
        result.push_back(0);
    }

    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ' ';
        cout << result[i];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

result = []
zeros = 0

for x in a:
    if x == 0:
        zeros += 1
    else:
        result.append(x)

result.extend([0] * zeros)

print(*result)