C++で一方の出現回数が他方の値以上となる配列内のペアを数える方法

問題の概要

正の整数で構成された配列が与えられます。この問題のゴールは、配列 arr[] の要素から選んだペア (A, B) のうち、「A の出現回数が B 以上であり、かつ B の出現回数が A 以上である」という条件を満たすペアの総数を求めることです。

具体的な例を使って確認してみましょう。

入力 − int arr[] = { 3, 3, 3, 5, 5, 6, 6 }

出力 − 一方の出現回数が他方の値以上となる配列内のペアの個数 − 1

説明 − この配列では 3 がちょうど 3 回出現しているため、ペア (3, 3) が条件を満たします。有効なペアはこの 1 つだけなので、答えは 1 となります。

入力 − int arr[] = { 3, 3, 3, 3, 3, 5, 5, 5, 6, 6 }

出力 − 一方の出現回数が他方の値以上となる配列内のペアの個数 − 3

説明 − この配列では 3 が 5 回、5 が 3 回出現しています。ここで条件を満たすのは (3, 3)、(3, 5)、(5, 3) の 3 つのペアです。3 の出現回数は 5 以上であり、5 の出現回数も 3 以上であるためです。したがって、答えは 3 になります。

プログラムで使用するアプローチ

まず、配列内の各要素の出現回数を格納する unordered_map を作成して値を設定します。続いて、範囲ベースの for ループでこのマップを走査し、各要素とその出現回数を取り出します。そして、条件を満たす組み合わせが見つかるたびにペアのカウントを 1 ずつ増やしていきます。

• 整数型の配列 arr[] を用意します。

• 関数 frequency_other_value(int arr[], int size) は、配列とそのサイズを受け取り、「A が少なくとも B 回出現し、B も少なくとも A 回出現する」ようなペア (A, B) の個数を返します。

• カウント用変数の初期値を 0 に設定します。

• arr[] の要素とその出現回数を管理するため、unordered_map<int, int> 型のマップ um を用意します。

• for ループでマップを走査し、各エントリのキー（要素の値 start）と値（出現回数 end）を取得します。その後、j を 1 から end まで動かしながら、um[j]（値 j の出現回数）が start 以上であるかを順に判定します。

• 条件を満たす組み合わせが見つかったら、カウントをインクリメントします。

• 最後にカウントを結果として返します。

アルゴリズムのポイント

この実装では、外側のループで「ある値とその出現回数」の組み合わせを列挙し、内側のループで「1 からその出現回数までの各値」の中に、出現回数が元の値以上のものが存在するかを確認しています。マップへのアクセスはすべて定数時間で行えるため、全体の計算量は要素数 N に対しておよそ O(N) 程度に抑えられ、非常に効率的です。

コード例

#include <bits/stdc++.h>
using namespace std;
int frequency_other_value(int arr[], int len){
    int count = 0;
    unordered_map<int, int> um;
    for (int i = 0; i < len; ++i){
        um[arr[i]]++;
    }
    for (auto it : um){
        int start = it.first;
        int end = it.second;
        for (int j = 1; j <= end; j++){
            if (um[j] >= start){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 3, 3, 3, 5, 5, 6, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs in an array such that frequency of one is at least value of other are: "<<frequency_other_value(arr, size);
    return 0;
}

出力

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

Count of pairs in an array such that frequency of one is at least value of other are: 1