প্রথম ইউনিক নম্বর খুঁজে বের করা C++-এ

সমস্যা বিবরণ

একটি ইন্টিজার কিউ দেওয়া আছে। সেটি থেকে প্রথম ইউনিক (একবার আসা) ইন্টিজার বের করতে হবে। ক্লাস FirstUnique ইমপ্লিমেন্ট করুন যেটিতে:

• কনস্ট্রাক্টর: 초기 কিউ দিয়ে ইনিশিয়ালাইজ।
• showFirstUnique(): প্রথম ইউনিক ইন্টিজার রিটার্ন করে, না থাকলে -1।
• add(value): কিউতে ভ্যালু যোগ করে।

উদাহরণ

ইনিশিয়াল: [2,3,5]

1. showFirstUnique() → ২
2. add(5) → কিউ: [2,3,5,5]
3. showFirstUnique() → ২
4. add(2) → কিউ: [2,3,5,5,2]
5. showFirstUnique() → ৩
6. add(3) → কিউ: [2,3,5,5,2,3]
7. showFirstUnique() → -১ (কোনো ইউনিক নেই)

অ্যালগরিদম: কিউ + ফ্রিকোয়েন্সি ম্যাপ

1. একটি queue<int> q রাখুন যাতে শুধু ইউনিক এলিমেন্ট থাকে (ইনসারশন অর্ডারে)।
2. একটি unordered_map<int, int> freq রাখুন ফ্রিকোয়েন্সি ট্র্যাক করতে।
3. ইনিশিয়ালাইজেশনে সব এলিমেন্টের ফ্রিকোয়েন্সি বড়ান, তারপর যেগুলোর ফ্রিকোয়েন্সি ১ সেগুলো কিউতে পুশ করুন।
4. showFirstUnique():
   • কিউর ফ্রন্ট এলিমেন্ট যতক্ষণ ফ্রিকোয়েন্সি > ১, ততক্ষণ পপ করুন।
   • কিউ খালি হলে -1, অন্যথায় ফ্রন্ট রিটার্ন করুন।
5. add(value):
   • ফ্রিকোয়েন্সি বড়ান।
   • যদি ফ্রিকোয়েন্সি ১ হয় (নতুন ইউনিক), কিউতে পুশ করুন।

C++ বাস্তবায়ন

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

class FirstUnique {
public:
    queue<int> q;
    unordered_map<int, int> freq;

    FirstUnique(vector<int>& nums) {
        for (int x : nums) freq[x]++;
        for (int x : nums) if (freq[x] == 1) q.push(x);
    }

    int showFirstUnique() {
        while (!q.empty() && freq[q.front()] > 1) q.pop();
        return q.empty() ? -1 : q.front();
    }

    void add(int value) {
        freq[value]++;
        if (freq[value] == 1) q.push(value);
    }
};

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

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: амর্টাইজড O(1) প্রতিটি অপারেশনের জন্য।
• স্থান জটিলতা: O(N) — ফ্রিকোয়েন্সি ম্যাপ ও কিউ।