मान लीजिए, हम एक डेटा संरचना बनाना चाहते हैं, जो कुछ संचालन का समर्थन करती है, इन कार्यों को ओ (1) समय की मात्रा में पूर्वनिर्मित किया जाना चाहिए। तो चलिए ये ऑपरेशन इस तरह हैं -
- सम्मिलित करें(x):संग्रह में x डालें
- निकालें(x):संग्रह से x हटाएं
- getRandom():यह उस संग्रह के रूप में यादृच्छिक तत्व ढूंढेगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- सरणी संख्याएं बनाएं
- एक नक्शा मी बनाएं
- एक फ़ंक्शन डालने को परिभाषित करें (), यह वैल लेगा,
- ret :=जब वैल m में न हो
- m[val] के अंत में अंकों का आकार डालें
- संख्याओं के अंत में { val, size of m[val] – 1} युग्म डालें
- रिटर्न रिटर्न
- एक फ़ंक्शन को परिभाषित करें निकालें(), यह वैल लेगा,
- ret :=जब वैल m में न हो
- यदि रिट गैर-शून्य है, तो −
- अंतिम =अंकों का अंतिम तत्व
- m [अंतिम की कुंजी] [अंतिम का मान] :=m का अंतिम तत्व [वैल]
- अंक [[m[val]] का अंतिम तत्व :=अंतिम
- m[val] से अंतिम तत्व हटाएं
- यदि m[val] खाली है, तो −
- m से वैल हटाएं
- अंकों से अंतिम तत्व हटाएं
- रिटर्न रिटर्न
- एक फ़ंक्शन को परिभाषित करें 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;
} इनपुट
Insert 10, 35, 20, 40, then get one random number, say 40, then remove 20, again get random element, that is say 35.
आउटपुट
40 35
