Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên phân biệt có trong dữ liệu đầu vào. Dữ liệu đầu vào có thể chứa nhiều số, mỗi số nằm trên một dòng riêng, và không có thông tin về số lượng số trước đó. Ví dụ: nếu đầu vào là: 1 2 1 3 2 Thì số lượng số phân biệt là 3 (các số 1, 2, 3).

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

Cách Sử dụng Set (C++ STL)

#include <iostream>
#include <set>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("khacnhau.inp", "r", stdin);
    freopen("khacnhau.out", "w", stdout);
    set<int> se;
    int n;
    while(cin >> n) {
        se.insert(n);
    }
    cout << se.size();
    return 0;
}

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

Sử dụng cấu trúc dữ liệu set của C++ STL. set lưu trữ các phần tử duy nhất và tự động sắp xếp. Mỗi khi đọc một số mới, ta chèn nó vào set. Nếu số đó đã tồn tại, set sẽ không thêm vào. Sau khi đọc hết dữ liệu, kích thước của set chính là số lượng số phân biệt. Độ phức tạp thời gian là O(N log N) do mỗi phép chèn vào set mất O(log N).

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

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   freopen("khacnhau.inp", "r", stdin);
   freopen("khacnhau.out", "w", stdout);
   unordered_set<int> se;
   int x;
   while(cin >> x) {
      se.insert(x);
   }
   cout << se.size() << endl;
   return 0;
}

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

Sử dụng unordered_set (còn gọi là Hash Set). Tương tự như set, nó lưu các phần tử duy nhất nhưng không sắp xếp. Phép chèn và kiểm tra tồn tại có độ phức tạp trung bình là O(1). Do đó, tổng thời gian chạy thường nhanh hơn set và đạt O(N) trong trường hợp trung bình.

Cách Sử dụng Hash Set với số lớn (Long Long)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("khacnhau.inp", "r", stdin);
    freopen("khacnhau.out", "w", stdout);
    long long x;
    unordered_set<long long> s;
    while (cin >> x) s.insert(x);
    cout << s.size();
    return 0;
}

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

Đây là biến thể của phương pháp Hash Set nhưng sử dụng long long thay vì int. Điều này đảm bảo rằng các số lớn (vượt quá giới hạn của int) vẫn được xử lý chính xác. Logic hoạt động tương tự như phương pháp trước.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết hiệu quả bằng cách sử dụng các cấu trúc dữ liệu tập hợp (Set) có sẵn trong thư viện chuẩn.
• Sử dụng unordered_set (Hash Set) thường hiệu quả hơn set (Cây đỏ-Đen) về mặt thời gian chạy với độ phức tạp O(N) so với O(N log N), trừ khi có yêu cầu đặc biệt về việc duy trì thứ tự phần tử.

Lỗi thường gặp

• Quên sử dụng tốc độ nhập xuất nhanh (ios::sync_with_stdio(false); cin.tie(NULL);) trong C++ khi làm việc với dữ liệu lớn có thể gây ra lỗi do hết thời gian (Time Limit Exceeded).
• Không xử lý đúng kiểu dữ liệu: Nếu các số đầu vào có thể vượt quá giới hạn của int (ví dụ $2^{31}-1$), cần sử dụng kiểu long long để tránh lỗi số học.