Javaでマジョリティ要素（多数派要素）を求める方法

問題概要

整数の配列が与えられたとき、その中でマジョリティ要素（多数派要素）、すなわち配列のサイズの半分を超える回数出現する要素を見つけることを考えます。まずは具体的な例で確認してみましょう。

入力例1 −

N = 8
A[ ] = { 1,2,4,3,3,1,1,5}

出力 −

1

説明 − 与えられた整数配列の中で最も多く出現している数字は「1」（3回出現）です。したがって、出力は「1」となります。

入力例2 −

N = 6
A[ ] = {1,5,4,4,1,1}

出力 −

1

説明 − この配列でも「1」が3回出現しており、全体の半分を超えています。よって出力として「1」を返します。

この問題を解くためのアプローチ

与えられた配列には複数の整数が含まれており、その中から最も頻繁に出現する要素を見つける必要があります。この問題を線形時間 O(n)・線形空間 O(n) で解くには、ハッシュマップ（HashMap）を使ったアプローチが有効です。

このアプローチでは、キーと値のペアで構成されるハッシュマップを作成します。キーには配列の各要素を、値にはその出現回数を格納します。その後、マップを走査しながら出現回数が N/2 を超える要素を探し、見つかればその値を結果として返します。

• サイズ N の配列を入力として受け取ります。

• 整数型関数 checkMajorityElement(int arr[], int N) は、配列とそのサイズを引数に受け取り、最大の出現頻度を持つ数値を返します。

• 配列のすべての要素について、キーを要素そのもの、値を出現頻度としたハッシュマップを作成します。

• マップを反復処理し、出現回数が N/2 を超える要素が存在すればその数値を結果として返します。該当する要素が存在しない場合は「-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

計算量の分析

このアルゴリズムでは、配列を一度走査してハッシュマップを構築するのに O(n)、その後マップを走査して条件を確認するのに O(n) かかるため、全体の時間計算量は O(n) となります。また、最悪ケース（すべての要素が異なる場合）ではハッシュマップに n 個のエントリが格納されるため、空間計算量も O(n) です。ソートを使う方法（O(n log n)）と比べて高速に動作する点が、このアプローチの大きな利点といえます。