मान लीजिए हमारे पास पूर्णांकों की एक कतार है, हमें उस कतार में पहला अद्वितीय पूर्णांक प्राप्त करना है। हमें FirstUnique नामक क्लास लागू करनी है: यह कतार में संख्याओं से प्रारंभ होगी। एक फ़ंक्शन showFirstUnique() परिभाषित करें, जो कतार के पहले अद्वितीय पूर्णांक का मान लौटाता है और यदि ऐसा कोई पूर्णांक नहीं है तो -1 लौटाता है। दूसरी विधि add(value) है जो मान को कतार में सम्मिलित करती है।
उदाहरण के लिए, यदि इनपुट है:
- [2,3,4] से प्रारंभ करें फिर फ़ंक्शन कॉल करें:
- showFirstUnique()
- add(5)
- showFirstUnique()
- add(2)
- showFirstUnique()
- add(3)
- showFirstUnique(),
तो आउटपुट क्रमशः 2, 2, 3, -1 होगा।
हल करने की विधि
हम एक कतार और एक आवृत्ति मैप का उपयोग करेंगे:
- कतार q और मैप cnt परिभाषित करें।
- प्रारंभकर्ता सरणी लेता है, प्रत्येक तत्व की गिनती बढ़ाता है, फिर गिनती 1 वाले तत्वों को कतार में डालता है।
- showFirstUnique(): जब तक कतार खाली नहीं है और सामने वाले तत्व की गिनती > 1 है, पॉप करें। यदि कतार खाली है तो -1 लौटाएं, अन्यथा सामने वाला तत्व।
- add(value): गिनती बढ़ाएं, यदि गिनती 1 हो गई तो कतार में डालें।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class FirstUnique { public: queue <int> q; map <int, int> cnt; FirstUnique(vector<int>& nums) { for (int i : nums) { cnt[i]++; } for (int i : nums) { if (cnt[i] == 1) { q.push(i); } } } 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); } }; main(){ vector<int> v = {2,3,5}; FirstUnique ob(v); cout << (ob.showFirstUnique()) << endl; ob.add(5); cout << (ob.showFirstUnique()) << endl; ob.add(2); cout << (ob.showFirstUnique()) << endl; ob.add(3); cout << (ob.showFirstUnique()) << endl; }
इनपुट
{2,3,5} ob.showFirstUnique(); ob.add(5); ob.showFirstUnique(); ob.add(2); ob.showFirstUnique(); ob.add(3); ob.showFirstUnique();
आउटपुट
2 2 3 -1
