मान लीजिए, हम एक डेटा संरचना बनाना चाहते हैं, जो कुछ ऑपरेशनों का समर्थन करती है, ये ऑपरेशन O(1) समय में किए जाने चाहिए। तो ये ऑपरेशन निम्नलिखित हैं -
- insert(x): संग्रह में x डालें
- remove(x): संग्रह से x हटाएं
- getRandom(): उस संग्रह से यादृच्छिक तत्व ढूंढें।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक सरणी nums बनाएं
- एक मैप m बनाएं
- एक फ़ंक्शन insert() परिभाषित करें, जो val लेगा,
- ret := जब val m में नहीं है
- nums के आकार को m[val] के अंत में डालें
- { val, m[val] का आकार - 1} जोड़ी को nums के अंत में डालें
- ret लौटाएं
- एक फ़ंक्शन remove() परिभाषित करें, जो val लेगा,
- ret := जब val m में नहीं है
- यदि ret शून्येतर है, तो -
- last = nums का अंतिम तत्व
- m[last की कुंजी][last का मान] := m[val] का अंतिम तत्व
- nums[m[val] का अंतिम तत्व] := last
- m[val] से अंतिम तत्व हटाएं
- यदि m[val] खाली है, तो -
- m से val हटाएं
- nums से अंतिम तत्व हटाएं
- ret लौटाएं
- एक फ़ंक्शन getRandom() परिभाषित करें
- संग्रह से एक यादृच्छिक तत्व लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; class RandomizedCollection { public: vector <pair <int, int>> nums; unordered_map <int, vector<int>> m; RandomizedCollection() { } bool insert(int val) { bool ret = m.find(val) == m.end(); m[val].push_back(nums.size()); nums.push_back({val, m[val].size() - 1}); return ret; } bool remove(int val) { bool ret = m.find(val) != m.end(); if(ret){ pair <int, int> last = nums.back(); m[last.first][last.second] = m[val].back(); nums[m[val].back()] = last; m[val].pop_back(); if(m[val].empty())m.erase(val); nums.pop_back(); } return ret; } int getRandom() { return nums[rand() % nums.size()].first; } }; main(){ RandomizedCollection ob; ob.insert(10); ob.insert(35); ob.insert(20); ob.insert(40); cout << (ob.getRandom()) << endl; ob.remove(20); cout << (ob.getRandom()) << endl; }इनपुट
10, 35, 20, 40 डालें, फिर एक यादृच्छिक संख्या प्राप्त करें, मान लें 40, फिर 20 हटाएं, फिर यादृच्छिक तत्व प्राप्त करें, जो मान लें 35 है।
आउटपुट
40 35
