Số duy nhất đầu tiên trong C++

Giới thiệu

Thiết kế lớp FirstUnique hỗ trợ:

• Khởi tạo với mảng số nguyên.
• showFirstUnique(): trả về số duy nhất đầu tiên trong hàng đợi, -1 nếu không có.
• add(value): thêm giá trị vào hàng đợi.

Ý tưởng: Hàng đợi + Hash Map đếm

• Map cnt lưu tần suất mỗi số.
• Queue q chỉ chứa các số có cnt == 1 theo thứ tự xuất hiện.
• showFirstUnique(): loại bỏ các phần tử đầu queue có cnt > 1, rồi trả về front hoặc -1.
• add(v): tăng cnt[v], nếu cnt[v] == 1 push vào queue.

Cài đặt C++

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

class FirstUnique {
    queue<int> q;
    unordered_map<int, int> cnt;
public:
    FirstUnique(vector<int>& nums) {
        for (int x : nums) cnt[x]++;
        for (int x : nums) if (cnt[x] == 1) q.push(x);
    }
    int showFirstUnique() {
        while (!q.empty() && cnt[q.front()] > 1) q.pop();
        return q.empty() ? -1 : q.front();
    }
    void add(int value) {
        cnt[value]++;
        if (cnt[value] == 1) q.push(value);
    }
};

int main() {
    vector<int> v = {2,3,5};
    FirstUnique ob(v);
    cout << ob.showFirstUnique() << ' '; // 2
    ob.add(5);
    cout << ob.showFirstUnique() << ' '; // 2
    ob.add(2);
    cout << ob.showFirstUnique() << ' '; // 3
    ob.add(3);
    cout << ob.showFirstUnique() << ' '; // -1
    return 0;
}

Phân tích

• Khởi tạo: O(N).
• showFirstUnique: O(1) amortized (mỗi phần tử bị pop tối đa 1 lần).
• add: O(1).
• Không gian: O(N).

LeetCode 1429 "First Unique Number".