ধরুন, আমরা একটি ডেটা স্ট্রাকচার তৈরি করতে চাই, যা কিছু ক্রিয়াকলাপকে সমর্থন করে, এই অপারেশনগুলিকে অবশ্যই O(1) সময়ের মধ্যে প্রিফর্ম করতে হবে। সুতরাং এই অপারেশনগুলি −
এর মতো হোক- ঢোকান(x):সংগ্রহে x সন্নিবেশ করান
- মুছুন(x):সংগ্রহ থেকে x মুছে দিন
- getRandom():এটি সংগ্রহের র্যান্ডম উপাদানটি খুঁজে পাবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি অ্যারে সংখ্যা তৈরি করুন
- একটি মানচিত্র তৈরি করুন m
- একটি ফাংশন সন্নিবেশ () সংজ্ঞায়িত করুন, এটি ভাল লাগবে,
- ret :=যখন val m না থাকে
- m[val] এর শেষে সংখ্যার আকার সন্নিবেশ করুন
- সংখ্যার শেষে { val, m[val] - 1} জোড়া সন্নিবেশ করুন
- রিটার্ন রিটার্ন
- একটি ফাংশন রিমুভ () সংজ্ঞায়িত করুন, এটি ভাল লাগবে,
- ret :=যখন val m না থাকে
- যদি ret অ-শূন্য হয়, তাহলে −
- শেষ =সংখ্যার শেষ উপাদান
- m[শেষের কী][শেষের মান] :=m[val] এর শেষ উপাদান
- সংখ্যা[[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
