Hiểu bài toán

Cho một mảng một chiều gồm các số nguyên (giá trị tuyệt đối <= 10^9, n <= 1000). Yêu cầu thống kê tần suất xuất hiện của từng số trong mảng và in ra danh sách các số khác nhau theo thứ tự tăng dần. Output gồm số lượng các giá trị khác nhau, sau đó là từng dòng chứa giá trị và số lần xuất hiện của nó.

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

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    map<long long, int> cnt;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        cnt[x]++; // Tự động tạo key nếu chưa có và tăng giá trị
    }

    cout << cnt.size() << "\n";
    for (auto &p : cnt) {
        cout << p.first << " " << p.second << "\n";
    }

    return 0;
}

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

Sử dụng cấu trúc dữ liệu map của C++ để lưu trữ các cặp (giá trị, số lần xuất hiện). Map trong C++ được cài đặt bằng cây đỏ-đen (Red-Black Tree), nên các phần tử luôn được sắp xếp theo thứ tự tăng dần của key. Khi duyệt qua mảng đầu vào, ta chỉ cần cập nhật map: cnt[x]++ sẽ tự động tăng số đếm nếu x đã tồn tại hoặc tạo mới nếu chưa có. Sau đó, in ra kích thước của map và duyệt qua từng phần tử của map để in ra giá trị và số lần xuất hiện.

Cách Sử dụng Map kết hợp Set (C++ STL)

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

int main() {
    int n;
    cin >> n;
    map<int, int> mp;
    set<int> distinct;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        mp[x]++;
        distinct.insert(x);
    }

    cout << distinct.size() << "\n";
    for (auto x : mp) {
        cout << x.first << " " << x.second << "\n";
    }

    return 0;
}

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

Cách tiếp cận này tách biệt việc đếm tần suất và việc lưu các giá trị khác nhau. Set 'distinct' lưu các giá trị duy nhất (tự động sắp xếp), Map 'mp' lưu tần suất. Tuy nhiên, cách này thừa thãi vì map đã tự động lưu key duy nhất và sắp xếp sẵn. Việc dùng set riêng làm tăng bộ nhớ và thời gian.

Cách Sử dụng Hash Map (unordered_map)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    unordered_map<long long, int> cnt;
    vector<long long> distinct;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        if (cnt[x] == 0) {
            distinct.push_back(x);
        }
        cnt[x]++;
    }

    sort(distinct.begin(), distinct.end());

    cout << distinct.size() << "\n";
    for (long long val : distinct) {
        cout << val << " " << cnt[val] << "\n";
    }

    return 0;
}

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

Sử dụng unorderedmap (cấu trúc băm) để đếm tần suất với độ phức tạp O(1) trung bình. Tuy nhiên, unorderedmap không tự sắp xếp, nên ta cần dùng một vector riêng để lưu các giá trị duy nhất (chỉ thêm khi lần đầu gặp), sau đó sort vector đó rồi in kết quả. Phức tạp hơn map thông thường.

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

Bài học kinh nghiệm

• Sử dụng map (hoặc unordered_map) là cách hiệu quả nhất để đếm tần suất và lưu trữ các phần tử khác nhau trong bài toán này.
• Map tự động sắp xếp các key theo thứ tự tăng dần, phù hợp với yêu cầu đầu ra của đề bài.
• Với n nhỏ (<= 1000), hiệu năng chênh lệch giữa map và unordered_map là không đáng kể, nên map thường được ưu tiên vì sự tiện lợi.

Lỗi thường gặp

• Quên in số lượng các giá trị khác nhau (K) ở dòng đầu tiên.
• Sử dụng mảng thường để đếm (ví dụ: int cnt[1000000]) vì giá trị đầu vào có thể lên tới 10^9, dẫn đến tràn bộ nhớ.
• In kết quả không đúng thứ tự tăng dần nếu sử dụng cấu trúc dữ liệu không được sắp xếp như unordered_map mà không sort lại.