मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है। कार्य दिए गए सरणी में किसी विशेष तत्व की अनुक्रमणिका ढूंढना है। उदाहरण के लिए,
इनपुट-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) में हल करने के लिए हम हैशमैप के दृष्टिकोण का उपयोग कर सकते हैं।
इस दृष्टिकोण में, हम एक अनियंत्रित नक्शा (एसटीएल लाइब्रेरी) बनाएंगे जिसमें कुंजी-मूल्य जोड़ी होगी जिसमें कुंजी एक तत्व होगी और मान तत्व की घटना होगी। मानचित्र के माध्यम से यात्रा करते समय हम संख्या की अधिकतम आवृत्ति पाएंगे और संख्या को आउटपुट के रूप में वापस कर देंगे।
-
इनपुट आकार 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