1. Идея

Нужно пройти по журналу слева направо и для каждого числа решить: оставить его или удалить.

По условию сохраняется только первое появление каждого значения. Значит:

• если число встретилось впервые — добавляем его в ответ;
• если такое число уже было раньше — пропускаем.

Чтобы быстро понимать, встречалось ли значение раньше, удобно хранить все уже увиденные числа в множестве.

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

1. Важен именно порядок первых появлений.

   Например, для последовательности 1 2 1 3 2 3 4 ответ должен быть 1 2 3 4, потому что:

   • 1 встретилось впервые — оставляем;
   • 2 встретилось впервые — оставляем;
   • второе 1 — удаляем;
   • 3 встретилось впервые — оставляем;
   • второе 2 — удаляем;
   • второе 3 — удаляем;
   • 4 встретилось впервые — оставляем.

2. Если проверять для каждого элемента, встречался ли он раньше, перебором всех предыдущих элементов, получится слишком медленно: до O(n^2).

3. Множество позволяет проверять наличие элемента в среднем за O(1), поэтому весь проход по массиву будет работать за линейное время.

3. Алгоритм

1. Считать n.
2. Считать n чисел.
3. Создать:
   • множество seen — значения, которые уже встречались;
   • список result — итоговая последовательность.
4. Для каждого числа x:
   • если x не содержится в seen:
     • добавить x в seen;
     • добавить x в result.
5. Вывести элементы result в одной строке через пробел.

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

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

Рассмотрим произвольное число x.

• Когда x встречается в последовательности первый раз, его ещё нет в множестве seen. Значит, алгоритм добавит x в result.
• После этого x сразу добавляется в seen.
• При любом следующем появлении x оно уже будет в seen, поэтому алгоритм его пропустит.

Значит, каждое значение попадает в ответ ровно один раз — при первом появлении.

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

Следовательно, алгоритм решает задачу правильно.

5. Сложность

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

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

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

    vector<long long> result;
    result.reserve(n);
    unordered_set<long long> seen;
    seen.reserve((size_t)n * 2);

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        if (seen.find(x) == seen.end()) {
            seen.insert(x);
            result.push_back(x);
        }
    }

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

    return 0;
}

7. Код на Python 3

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

seen = set()
result = []

for x in a:
    if x not in seen:
        seen.add(x)
        result.append(x)

print(*result)