ধরা যাক আমাদের পূর্ণসংখ্যার একটি অ্যারে আছে। কাজ হল প্রদত্ত অ্যারেতে একটি নির্দিষ্ট উপাদানের সূচক খুঁজে বের করা। উদাহরণস্বরূপ,
ইনপুট-1 −
N = 8 A[ ] = { 1,2,4,3,3,1,1,5} আউটপুট −
1
ব্যাখ্যা − প্রদত্ত পূর্ণসংখ্যার বিন্যাসে, সবচেয়ে বেশি প্রদর্শিত সংখ্যা হল '1'। সুতরাং আউটপুট হল '1'।
ইনপুট-2 −
N = 6 A[ ] = {1,5,4,4,1,1} আউটপুট −
1
ব্যাখ্যা − প্রদত্ত পূর্ণসংখ্যার বিন্যাসে, সবচেয়ে বেশি প্রদর্শিত সংখ্যা হল '1'। এইভাবে আমরা আউটপুট '1' ফেরত দিতে পারি।
এই সমস্যা সমাধানের পদ্ধতি
প্রদত্ত অ্যারেটিতে একাধিক পূর্ণসংখ্যা রয়েছে যেখানে আমাদের অ্যারেতে উপস্থিত সর্বাধিক ঘন ঘন উপাদানটি খুঁজে বের করতে হবে। লিনিয়ার টাইম O(n) এবং লিনিয়ার স্পেস O(n) এ এই সমস্যাটি সমাধান করতে আমরা একটি হ্যাশম্যাপের পদ্ধতি ব্যবহার করতে পারি।
এই পদ্ধতিতে, আমরা কী-মানের জোড়া নিয়ে একটি অ-ক্রমবিহীন মানচিত্র (STL লাইব্রেরি) তৈরি করব যেখানে কী হবে একটি উপাদান এবং মানটি হবে উপাদানটির উপস্থিতি। মানচিত্রের মধ্য দিয়ে যাওয়ার সময় আমরা সংখ্যাটির সর্বাধিক উপস্থিতি খুঁজে পাব এবং সংখ্যাটিকে আউটপুট হিসাবে ফিরিয়ে দেব।
-
N
আকারের একটি অ্যারে ইনপুট নিন -
একটি পূর্ণসংখ্যা ফাংশন maxOccurrence(int A[], int size) একটি অ্যারে এবং এর আকার একটি ইনপুট হিসাবে নেয় এবং সর্বাধিক ফ্রিকোয়েন্সি সহ সংখ্যাগুলি প্রদান করে৷
-
অ্যারের সমস্ত উপাদানের একটি হ্যাশম্যাপ তৈরি করা একটি উপাদান হিসাবে কী এবং এর ফ্রিকোয়েন্সি হিসাবে মান নিয়ে৷
-
মানচিত্রের উপর পুনরাবৃত্তি করুন এবং পরীক্ষা করুন যে কোনো উপাদানের সর্বাধিক ফ্রিকোয়েন্সি আছে কিনা তারপর ফলাফলটি সংখ্যা হিসাবে ফেরত দিন। অন্যথায়, যদি অ্যারেতে কোনো সংখ্যা না থাকে তাহলে '-1' রিটার্ন করুন।
উদাহরণ
def checkMajorityElement(arr, N):
mp = {}
for i in range(0, N):
if arr[i] in mp.keys():
mp[arr[i]] += 1
else:
mp[arr[i]] = 1
for key in mp:
if mp[key] > (N / 2):
return key
return -1
print("Enter size of array:")
N = int(6)
print("Enter elements of array:")
arr = [2,1,1,2,2,2]
ans = checkMajorityElement(arr, N)
if ans != -1:
print("Majority Element is: %d" % ans)
else:
print("No majority element in array") আউটপুট
উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
Enter size of array: 6 Enter elements of array: 2 1 1 2 2 2 Majority Element is: 2
