Hiểu bài toán

Cho một danh sách N số nguyên dương đại diện cho số IP của N nhân viên. Mỗi nhân viên có một số IP duy nhất. Nhiệm vụ là tìm số nguyên dương nhỏ nhất (bắt đầu từ 1) không xuất hiện trong danh sách đã cho. N có thể lên tới 500,000 và các số IP có thể rất lớn.

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

Cách Sử dụng Hash Map (hoặc Hash Set)

#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    unordered_set<long long> s;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        s.insert(x);
    }
    long long ans = 1;
    while (s.count(ans)) ans++;
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(N) trong trường hợp trung bình, tối đa O(N^2) nếu gặp nhiều va chạm hash
• Space Complexity: O(N)

Sử dụng một bộ chứa (unordered_set) để lưu trữ các số IP hiện có. Sau đó, ta bắt đầu từ số 1 và kiểm tra liên tục xem số đó có trong bộ chứa không. Nếu có, tăng số lên 1 và tiếp tục. Cách này đơn giản và hiệu quả về thời gian nếu ta may mắn tìm được số thiếu ở nhỏ.

Cách Sử dụng Mảng đánh dấu (Bitset)

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

bool d[5000005];
long long a[500005];

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

    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        if(a[i] > 0 && a[i] <= 5000000) d[a[i]] = true;
    }

    for(int i=1;;i++)
    {
        if(!d[i])
        {
            cout << i;
            break;
        }
    }
}

• Time Complexity: O(N + K) (Với K là kích thước mảng đánh dấu ~5 triệu)
• Space Complexity: O(K)

Sử dụng một mảng boolean (hoặc bitset) để đánh dấu các số đã xuất hiện. Ta chỉ cần quét qua mảng từ 1 để tìm số đầu tiên chưa được đánh dấu. Phương pháp này có độ phức tạp thời gian ổn định (không phụ thuộc vào may mắn như hash set) nhưng chỉ hiệu quả nếu ta biết trước giới hạn của số IP hoặc phân tích được đề bài cho thấy số IP không vượt quá quá lớn.

Cách Sử dụng Map (hoặc Quicksort)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    map <int, bool> ok;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        ok[a] = 1;
    }
    for (int i = 1; i <= 1e7; i++)
        if (!ok[i])
            return cout << i, 0;
}

• Time Complexity: O(N log N) hoặc O(N log M)
• Space Complexity: O(N)

Sử dụng cấu trúc dữ liệu Map (cây đỏ-đen) để lưu trữ các số IP. Map cho phép tìm kiếm theo khóa trong thời gian O(log N). Ta duyệt từ 1 và kiểm tra sự tồn tại trong Map. Đây là cách tiếp cận 'an toàn' nhưng chậm hơn so với Hash Set.

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

Bài học kinh nghiệm

• Bài toán là biến thể của bài toán tìm số nguyên dương nhỏ nhất thiếu trong mảng (First Missing Positive).
• Nếu ta quét từ 1 trở lên, số đầu tiên không xuất hiện trong danh sách chính là đáp án.
• Giá trị của N (500,000) đủ lớn để cần chú ý đến hiệu năng nhập/xuất (I/O) và thuật toán.

Lỗi thường gặp

• Đọc input chậm: Với N lớn, nên dùng ios_base::sync_with_stdio(false); cin.tie(0); trong C++.
• Nếu số IP có thể âm, cần bỏ qua chúng khi đánh dấu mảng hoặc kiểm tra.
• Nếu dùng mảng tĩnh, cần dự đoán kích thước tối đa để tránh lỗi bộ nhớ.