Javaのマジョリティ要素

整数の配列を指定したとしましょう。タスクは、指定された配列内の特定の要素のインデックスを見つけることです。たとえば、

入力-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