ধরুন আমাদের একটি ডেটা স্ট্রাকচার রয়েছে যা গড়ে O(1) সময়ে নিম্নলিখিত সমস্ত ক্রিয়াকলাপগুলিকে সমর্থন করে৷
-
insert(val) − এটি সেটে একটি আইটেম ভাল সন্নিবেশ করবে যদি এটি ইতিমধ্যে উপস্থিত না থাকে৷
-
remove(val) - এটি উপস্থাপন করলে সেট থেকে একটি আইটেম ভ্যাল সরিয়ে ফেলবে।
-
getRandom - এটি বর্তমান উপাদানগুলির সেট থেকে একটি এলোমেলো উপাদান ফিরিয়ে দেবে। প্রতিটি উপাদানের ফেরত পাওয়ার একই সম্ভাবনা থাকতে হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
আরম্ভ করার জন্য, একটি অভিভাবক মানচিত্র, এবং উপাদান অ্যারে সংজ্ঞায়িত করুন
-
সন্নিবেশ () ফাংশনের জন্য, এটি ইনপুট হিসাবে ভাল লাগবে
-
যদি প্যারেন্ট ম্যাপে val উপস্থিত না থাকে, অথবা parent[val] =0, তাহলে উপাদানগুলিতে val ঢোকান, এবং প্যারেন্ট[val] :=1 সেট করুন এবং সত্যে ফিরে আসুন
-
-
ফেরত মিথ্যা
-
রিমুভ() পদ্ধতির জন্য, এটি অপসারণ করতে ভ্যাল লাগবে
-
যদি val প্যারেন্ট ম্যাপে উপস্থিত না থাকে, অথবা parent[val] =0, তাহলে মিথ্যা ফেরত দিন
-
সেট প্যারেন্ট[ভাল] :=0
-
সূচক :=উপাদান অ্যারেতে ভ্যালের সূচক
-
যদি সূচক উপাদানগুলির দৈর্ঘ্যের সমান না হয় - 1
-
temp :=উপাদানের শেষ উপাদান
-
উপাদানগুলির শেষ উপাদান সেট করুন :=val
-
সেট উপাদান [সূচী] :=temp
-
-
উপাদানগুলির শেষ উপাদান মুছুন
-
getRandom() পদ্ধতি উপাদান অ্যারেতে উপস্থিত যেকোনো র্যান্ডম মান ফিরিয়ে দেবে
উদাহরণ(পাইথন)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
randomclass RandomizedSet(অবজেক্ট):def __init__(self):self.present ={} self.elements =[] def insert(self, val):যদি val self.present বা self.present[val] তে না থাকে ==0:self.elements.append(val) self.present[val] =1 রিটার্ন True return False def remove(self, val):যদি val না self.present বা self.present[val] ==0:রিটার্ন False self.present[val] =0 index =self.elements.index(val) যদি index!=len(self.elements)-1:temp =self.elements[-1] self.elements[-1] =val self.elements[index]=temp self.elements.pop() রিটার্ন True def getRandom(self):রিটার্ন random.choice(self.elements)ob =RandomizedSet()print(ob.insert(1))print(ob. .remove(2))print(ob.insert(2))print(ob.getRandom())print(ob.remove(1))print(ob.insert(2))print(ob.getRandom()) ইনপুট
ক্লাস শুরু করুন, তারপর insert(), remove(), getRandom() ফাংশনগুলিকে কল করুন। বাস্তবায়ন দেখুন।
আউটপুট
TrueFalseTrue2TrueFalse2
