C++で配列内にb回出現する唯一の要素を効率的に見つける方法

問題概要

この問題では、サイズnの配列arr[]と2つの整数a、bが与えられます。求めるのは、配列内でちょうどb回出現する唯一の要素です。

配列内のすべての値はa回出現しますが、ただ1つの値だけがb回出現します。私たちのタスクは、この特別な値を見つけることです。

問題例

具体例を使って問題を理解しましょう。

入力:

arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1, 1, 1}、a = 4、b = 3

出力:

5

この例では、3は4回、1は4回出現していますが、5だけが3回(b回)出現しているため、答えは5となります。

解決アプローチ

方法1: 単純なカウント方式(O(N²))

最もシンプルな解法は、各要素の出現回数を数えて2次元のマトリックスに格納し、その後マトリックスを走査して出現頻度がbである値を探す方法です。しかし、このアプローチの時間計算量はO(N²)となり、大きな配列に対しては非効率です。

方法2: 合計を利用した効率的な数式アプローチ

より効果的な方法は、数学的な性質を利用することです。手順は以下の通りです。

1. 配列内のすべての一意な要素(重複を除いた要素)の合計を求めます。
2. その合計にaを掛けます。
3. 配列全体の合計を、上記の値から引きます。
4. 結果を(a − b)で割ります。

この計算の背景にある理屈は次の通りです。すべての要素がa回ずつ出現していれば「a × 一意な要素の合計」が配列全体の合計と一致します。しかし、目的の値だけはb回しか出現しないため、差分として「(a − b) × 目的の値」が残ります。これを(a − b)で割ることで、目的の値を導き出せるのです。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
int findbFreqVal(int arr[], int n, int a, int b){
    unordered_set<int> uniqueVal;
    int uniqueValSum = 0, arrSum = 0;
    for (int i = 0; i < n; i++) {
        if (uniqueVal.find(arr[i]) == uniqueVal.end()) {
            uniqueVal.insert(arr[i]);
            uniqueValSum += arr[i];
        }
        arrSum += arr[i];
    }
    uniqueValSum = a * uniqueValSum;
    return ((uniqueValSum - arrSum) / (a - b));
}
int main(){
    int arr[] = { 4, 4, 4, 31, 8, 8, 8, 5, 5, 5};
    int a = 3, b = 1;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The value of the array that appears b times is "<<findbFreqVal(arr, n, a, b);
    return 0;
}

出力

The value of the array that appears b times is 31

まとめ

このプログラムでは、unordered_setを使って一意な要素を管理し、配列を一度走査するだけで一意な要素の合計と配列全体の合計を同時に計算しています。これにより、時間計算量はO(N)、空間計算量もO(N)で済み、単純なカウント方式よりも大幅に効率的な解法となっています。