জাভাতে সংখ্যাগরিষ্ঠ উপাদান

ধরা যাক আমরা পূর্ণসংখ্যার একটি অ্যারে দিয়েছি। কাজ হল প্রদত্ত অ্যারেতে একটি নির্দিষ্ট উপাদানের সূচক খুঁজে বের করা। উদাহরণস্বরূপ,

ইনপুট-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' রিটার্ন করুন।

উদাহরণ

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
class Majority_Element{
   public static int checkMajorityElement(int arr[], int N){
      Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
      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<Integer, Integer> 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("Enter size of array:");
      int N = 6;
      int arr[] = {2,1,1,2,2,2};
      System.out.println("Enter elements of array:");
      for (int i = 0; i < N; i++)
         arr[i] = sc.nextInt();
      int ans = checkMajorityElement(arr, N);
      if (ans != -1)
         System.out.println("Majority Element is: " + ans);
      else
         System.out.println("No majority element in array");
   }
}

আউটপুট

উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,

Enter size of array: 6
Enter elements of array: 2 1 1 2 2 2
Majority Element is: 2