র্যান্ডোমাইজড কলেকশন (ডুপ্লিকেট অনুমোদিত)
একটি ডেটা স্ট্রাকচার তৈরি করতে হবে যা নিচের অপারেশনগুলো O(1) সময়ে সমর্থন করে:
insert(val): মান যোগ করুন, নতুন হলেtrueফেরত দিনremove(val): মান মুছুন, সফল হলেtrueফেরত দিনgetRandom(): কালেকশন থেকে একটি র্যান্ডোম উপাদান ফেরত দিন
ডুপ্লিকেট মান অনুমোদিত।
সমাধানের পদ্ধতি
- ভেক্টর
nums: প্রতিটি এন্ট্রি হলোpair<value, index_in_map_vector> - আনঅর্ডার্ড ম্যাপ
m: কী = মান, মান = সূচকগুলোর ভেক্টর (যেগুলোnums-এ অবস্থান করে) - ইনসার্ট:
nums-এ যোগ করুন, ম্যাপে সূচক যোগ করুন - রিমুভ: শেষ উপাদানটি মুছে ফেলা উপাদানের জায়গায় স왪 করুন, তারপর পপ করুন। ম্যাপ আপডেট করুন
- গেটর্যান্ডম:
nums[rand() % size].firstফেরত দিন
C++ কোড উদাহরণ
#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, (int)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;
}
};
int 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;
return 0;
}
ইনপুট
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
