समस्या विवरण
मान लीजिए हमारे पास पूर्णांकों की एक सरणी दी गई है। कार्य दिए गए सरणी में एक विशेष तत्व का सूचकांक ढूंढना है।
उदाहरण
इनपुट-1
N = 8
A[] = { 1,2,4,3,3,1,1,5}आउटपुट
1व्याख्या - दिए गए पूर्णांकों की सरणी में, सबसे अधिक बार आने वाली संख्या '1' है। इस प्रकार आउटपुट '1' है।
समस्या हल करने का दृष्टिकोण
दिए गए सरणी में कई पूर्णांक हैं जिनमें हमें सरणी में मौजूद सबसे अधिक बार आने वाले तत्व को ढूंढना है। इस समस्या को रैखिक समय O(n) और रैखिक स्पेस O(n) में हल करने के लिए हम हैशमैप के दृष्टिकोण का उपयोग कर सकते हैं।
इस दृष्टिकोण में, हम एक अनऑर्डर्ड मैप (STL लाइब्रेरी) बनाएंगे जिसमें कुंजी-मान जोड़ी होगी जिसमें कुंजी एक तत्व होगी और मान तत्व की घटना होगी। मैप के माध्यम से पार करते समय हम संख्या की अधिकतम घटना ढूंढेंगे और आउटपुट के रूप में संख्या वापस करेंगे।
- आकार N की एक सरणी का इनपुट लें
- एक पूर्णांक फ़ंक्शन maxOccurrence(int A[], int size) एक सरणी और उसके आकार को इनपुट के रूप में लेता है और अधिकतम आवृत्ति वाली संख्या को वापस करता है।
- सरणी के सभी तत्वों का हैशमैप बनाएं जिसमें कुंजी एक तत्व के रूप में और मान उसकी आवृत्ति के रूप में हो।
- मैप पर पुनरावृति करें और जांचें कि क्या किसी तत्व की सबसे अधिक आवृत्ति है तो परिणाम को संख्या के रूप में वापस करें। अन्यथा, यदि सरणी में कोई संख्या मौजूद नहीं है तो '-1' वापस करें।
उदाहरण
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
class Majority_Element{
public static int checkMajorityElement(int arr[], int N){
Map mp = new HashMap();
for (int i = 0; i < N; i++){
if (mp.containsKey(arr[i]))
mp.put(arr[i], mp.get(arr[i]) + 1);
else
mp.put(arr[i], 1);
}
for (Map.Entry entry : mp.entrySet()){
if (entry.getValue() > (N / 2))
return entry.getKey();
}
return -1;
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
System.out.println("सरणी का आकार दर्ज करें:");
int N = 6;
int arr[] = {2,1,1,2,2,2};
System.out.println("सरणी के तत्व दर्ज करें:");
for (int i = 0; i < N; i++)
arr[i] = sc.nextInt();
int ans = checkMajorityElement(arr, N);
if (ans != -1)
System.out.println("मेजोरिटी एलिमेंट है: " + ans);
else
System.out.println("सरणी में कोई मेजोरिटी एलिमेंट नहीं है");
}
} आउटपुट
सरणी का आकार दर्ज करें: 6
सरणी के तत्व दर्ज करें: 2 1 1 2 2 2
मेजोरिटी एलिमेंट है: 2