C++で整数配列から上位K個の高頻度要素を見つけるプログラムの作成方法

サイズNの整数配列とキーKが与えられたとき、配列の中で最も頻繁に出現する上位K個の要素を出力するのが本記事の課題です。まずは具体例で問題を確認しましょう。

入出力例

入力例1

N = 6
K = 2
arr[ ] = {1, 1, 1, 2, 2, 3}

出力

1 2

説明: 与えられた整数配列の中で、出現回数が多い上位K=2個の要素は {1, 2} です。

入力例2

N = 2
K = 1
arr[ ] = {1, 2}

出力

1

説明: この配列では各要素が1回ずつしか出現しないため、上位K=1個の要素として先頭の {1} が返されます。

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

与えられた整数配列の中から、最も多く繰り返し出現する数値を見つけ出して返す必要があります。キーKは、結果として返すべき上位K個の要素の数を表します。

アプローチは非常にシンプルです。まずハッシュテーブルを作成し、キーとして配列の各要素、値としてその出現回数を格納します。その後、マップ全体を出現回数でソートし、頻度の高い順に上位K個の要素を結果として返します。

• NとN個の要素からなる配列を入力として受け取ります。

• 配列arr[ ]とキーKを受け取り、上位K個の高頻度要素を返す関数 topKfrequent(int *arr, int n, int k) を定義します。

• すべての要素とその出現回数を、キーと値のペアとしてハッシュマップに格納します。

• ハッシュマップ内のすべての値(出現回数)をソートします。

• マップを出現回数の降順に並べ替えるためのbool型ヘルパー関数(compare)を用意します。

• ハッシュマップ内のすべての要素を走査し、最も頻度の高い上位K個の要素を出力します。

実装例(C++コード)

#include<bits/stdc++.h>
using namespace std;

// 出現回数(ペアの第二要素)で降順にソートする比較関数
bool compare(pair<int,int>& a, pair<int,int>& b){
   return a.second > b.second;
}

// 上位K個の高頻度要素を出力する関数
void topKfrequent(int* arr, int n, int k){
   unordered_map<int,int> mp;
   // 各要素の出現回数をカウント
   for(int i = 0; i < n; i++){
      mp[arr[i]]++;
   }
   // マップの内容をベクトルにコピーしてソート
   vector<pair<int,int>> v(mp.begin(), mp.end());
   sort(v.begin(), v.end(), compare);
   // 頻度の高い順に上位K個の要素を出力
   for(int i = 0; i < k; i++){
      cout << v[i].first << " ";
   }
}

int main(){
   int N = 5;
   int arr[N] = {1, 1, 3, 2, 2};
   int k = 2;
   topKfrequent(arr, N, k);
   return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

1 2

この例では、配列 {1, 1, 3, 2, 2} の中で「1」と「2」がそれぞれ2回出現しており、これらが上位K=2個の最頻出要素となります。なお、両者は同じ出現回数のため、表示順序はハッシュマップの内部実装によって入れ替わる場合がある点に注意してください。

計算量の目安

時間計算量はO(N + M log M)です(Nは配列の要素数、Mはユニークな要素数)。ハッシュマップへのカウント登録にO(N)、ソートにO(M log M)かかります。空間計算量はO(N)です。