Hiểu bài toán

Bài toán yêu cầu xử lý nhiều test case. Với mỗi test case, cho một dãy số gồm n số nguyên. Nhiệm vụ là in ra các phần tử khác nhau của dãy theo thứ tự xuất hiện lần đầu tiên (từ trái sang phải). Ví dụ: với dãy [2, 1, 2, 3, 1], kết quả là [2, 1, 3].

Các cách tiếp cận

Cách Sử dụng Map để đếm tần suất

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 7;
int a[N], n, t;

void xuli() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    map<int, int> ma;
    for (int i = 1; i <= n; ++i) {
        if (ma[a[i]] == 0) cout << a[i] << ' ';
        ++ma[a[i]];
    }
    cout << endl;
}

int main() {
    if (fopen("BDEL.inp", "r")) {
        freopen("BDEL.inp", "r", stdin);
        freopen("BDEL.out", "w", stdout);
    }
    cin >> t;
    for (int i = 1; i <= t; ++i) xuli();
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Approach này sử dụng map<int, int> để lưu tần suất xuất hiện của các phần tử. Khi duyệt qua mảng, nếu phần tử hiện tại chưa có trong map (giá trị mặc định là 0), ta in nó ra và tăng biến đếm lên. Cấu trúc map trong C++ mặc định sắp xếp keys, nhưng do ta chỉ in phần tử khi đếm từ 0 lên 1 và duyệt theo thứ tự mảng ban đầu nên thứ tự in ra vẫn đúng theo yêu cầu. Tuy nhiên, độ phức tạp log n của map làm cho cách này chậm hơn so với hash set.

Cách Sử dụng Hash Set (Unordered Set)

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("BDEL.inp", "r", stdin);
    freopen("BDEL.out", "w", stdout);

    unordered_set<int> v;
    vector<int> s;
    int t, n, x;
    cin >> t;

    while (t--) {
        cin >> n;
        v.clear();
        s.clear();
        s.reserve(n);
        for (int i = 0; i < n; i++) {
            cin >> x;
            if (v.insert(x).second) {
                s.push_back(x);
            }
        }
        for (int x : s) cout << x << " ";
        cout << "\n";
    }
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là approach tối ưu. Dùng unordered_set (Hash Set) để kiểm tra sự tồn tại của phần tử trong thời gian O(1) trung bình. Dùng một vector s để lưu trữ các phần tử duy nhất theo thứ tự xuất hiện. Khi duyệt mảng, nếu v.insert(x).second là true (tức là phần tử chưa tồn tại trong set), ta thêm nó vào vector s. Cuối cùng in ra vector s. Cách này hiệu quả về mặt thời gian so với map.

Cách Sử dụng Vector và Find (Slower)

#include <bits/stdc++.h>
using namespace std;

void xuli() {
    int n; cin >> n;
    vector<int> res;
    for (int i = 0; i < n; ++i) {
        int a; cin >> a;
        // Kiểm tra xem a đã có trong res chưa
        bool found = false;
        for (int x : res) {
            if (x == a) {
                found = true;
                break;
            }
        }
        if (!found) res.push_back(a);
    }
    for (int x : res) cout << x << " ";
    cout << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) xuli();
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là cách tiếp cận đơn giản nhất nhưng không hiệu quả. Ta dùng một vector để lưu kết quả. Với mỗi phần tử mới đọc vào, ta duyệt qua vector kết quả để kiểm tra xem nó đã xuất hiện chưa. Nếu chưa thì thêm vào. Độ phức tạp thời gian là O(n^2) do với mỗi phần tử, ta duyệt O(n) lần. Với n lớn (ví dụ 50,000), cách này chắc chắn bị TLE (Time Limit Exceeded). Tuy nhiên, nó là một cách suy nghĩ cơ bản đầu tiên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề cốt lõi là tìm các phần tử duy nhất theo thứ tự xuất hiện (First Occurrence). Hash Set (unordered_set) là cấu trúc dữ liệu lý tưởng để kiểm tra sự tồn tại với thời gian O(1).
• Luôn sử dụng ios::sync_with_stdio(false); cin.tie(0); trong C++ để tăng tốc độ nhập xuất dữ liệu, đặc biệt quan trọng trong các bài toán có số lượng test case lớn hoặc dữ liệu vào lớn.

Lỗi thường gặp

• Sử dụng std::set (Tree Set) thay vì std::unordered_set sẽ làm độ phức tạp tăng lên O(n log n) thay vì O(n) trung bình.
• Quên xử lý việc reset dữ liệu cho mỗi test case (ví dụ: clear vector, clear set) dẫn đến lỗi dữ liệu thừa các test case trước.
• Đọc sai định dạng input hoặc output (ví dụ: in thừa dấu cách cuối dòng có thể gây lỗi Presentation Error tùy từng judge).