First Unique Number – หาตัวเลขที่ไม่ซ้ำตัวแรกในคิว C++

ปัญหา: First Unique Number

ออกแบบคลาส FirstUnique รองรับ:

• FirstUnique(nums) – เริ่มต้นด้วยอาร์เรย์ตัวเลข
• showFirstUnique() – คืนตัวเลขที่ไม่ซ้ำตัวแรกในคิว, ไม่มี → -1
• add(value) – เพิ่มตัวเลขเข้าไปในคิว

ตัวอย่าง

Init: [2,3,5]
showFirstUnique() → 2
add(5) → queue: [2,3,5,5]
showFirstUnique() → 2
add(2) → queue: [2,3,5,5,2]
showFirstUnique() → 3
add(3) → queue: [2,3,5,5,2,3]
showFirstUnique() → -1

แนวทางแก้ปัญหา: Queue + Hash Map

โครงสร้างข้อมูล

• queue<int> q – เก็บตัวเลขที่ "เป็น unique ณ ตอนที่เพิ่ม" ตามลำดับ
• unordered_map<int, int> cnt – นับความถี่ของแต่ละตัวเลข

การทำงาน

• Initialization: นับความถี่ทั้งหมด → push เข้า q เฉพาะตัวที่ cnt == 1
• showFirstUnique(): Pop ออกจาก q จนกว่าจะเจอตัวที่ cnt == 1 (หรือ q ว่าง → -1)
• add(value): cnt[value]++ → ถ้า cnt กลายเป็น 1 → push เข้า q

ตัวอย่างโค้ด 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 fu(v);
    cout << fu.showFirstUnique() << ' '; // 2
    fu.add(5);
    cout << fu.showFirstUnique() << ' '; // 2
    fu.add(2);
    cout << fu.showFirstUnique() << ' '; // 3
    fu.add(3);
    cout << fu.showFirstUnique() << ' '; // -1
    return 0;
}

ความซับซ้อน

พื้นที่: O(U) – U = จำนวนค่าที่ไม่ซ้ำ

ข้อสังเกต

• LeetCode 1429 (First Unique Number)
• Amortized O(1) เพราะแต่ละ element ถูก pop สูงสุด 1 ครั้ง
• ใช้ unordered_map เร็วกว่า map
• Queue เก็บ "ผู้สมัคร" – ตัวที่เคย unique ตอนเพิ่ม แต่อาจกลายเป็น duplicate ภายหลัง