C++で配列要素と指定した数値の平均の出現回数をカウントする方法

問題の概要

整数要素を含む配列 arr[] と整数 num が与えられます。この問題の目標は、各要素 arr[i] と num の平均を求め、その平均値が元の配列 arr[] 内に何回出現するかをカウントして出力することです。

たとえば、配列 arr[] が [5, 2, 3]、num が 2 の場合、平均値は [3, 2, 2] となり、それぞれが arr[] 内に出現する回数は [1, 1, 1] になります。

入力例 1

arr[] = { 1, 6, 4, 3, 6, 4 }
num = 2

出力例 1

1 2 1 0 2 1

ゼロ以外の出現回数を持つ要素の合計：5

説明

num は 2 であり、arr[] 内の各要素との平均は次のとおりです。
[ 1, 4, 3, 2, 4, 3 ]
これらが arr[] 内に出現する回数は次のとおりです。
[ 1, 2, 1, 0, 2, 1 ]

入力例 2

arr[] = { 4, 8, 24, 16, 20, 40 }
num = 4

出力例 2

1 0 0 0 0 0

ゼロ以外の出現回数を持つ要素の合計：1

説明

num は 4 であり、arr[] 内の各要素との平均は次のとおりです。
[ 4, 6, 14, 10, 12, 22 ]
これらが arr[] 内に出現する回数は次のとおりです。
[ 1, 0, 0, 0, 0, 0 ]

解決アプローチ

このアプローチでは、配列内の一意な数値とその出現回数を格納するためのマップ（std::map）を作成します。次に、num と各要素の平均を計算し、その平均がマップに存在する場合には、対応する出現回数を結果配列に記録していきます。

• 整数型の配列 arr[] と整数 num を入力として受け取ります。
• 関数 occurrence_average(int arr[], int size, int num) は、入力配列と num を受け取り、各平均が arr[] 内に出現する回数の配列を出力します。戻り値としては、ゼロ以外の出現回数を持つ要素の個数を返します。
• 初期値 count = 0 を用意します。
• arr[] 内の一意な数値ごとの出現回数を格納する map<int, int> 型の map_pair を宣言します。
• 各平均の出現回数を格納するための配列 total[] を用意します。
• for ループで i = 0 から i < size まで配列 arr[] を走査し、map_pair[arr[i]]++ によって各要素に対応するキーの値をインクリメントします。
• ループが終わった時点で、マップには一意な数値がキーとして、arr[] 内での出現回数が値として格納されています。
• 再び for ループで配列を走査し、num と各要素の平均を計算して temp に保存します。
• map_pair.find(temp) != map_pair.end() によって temp が map_pair に存在するかどうかを確認し、存在すればその出現回数を total 配列に格納します。
• total 配列を出力して、arr[] 内で出現した平均の回数を表示します。同時に、ゼロ以外の要素ごとに count をインクリメントします。
• 最後に count を結果として返します。

C++ 実装例

#include<bits/stdc++.h>
using namespace std;
int occurrence_average(int arr[], int size, int num){
    int count = 0;
    map<int,int> map_pair;
    int total[size] = {0};
    int val, av;
    for (int i = 0; i < size; i++){
       if (map_pair[arr[i]] == 0){
          map_pair[arr[i]] = 1;
       } else {
          map_pair[arr[i]]++;
       }
    }
    for (int i = 0; i < size; i++){
       int temp = int((arr[i] + num) / 2);
       if(map_pair.find(temp) != map_pair.end()){
          int set = map_pair[temp];
          total[i] = set;
       }
    }
    cout<<endl;
    for(int i=0;i<size;i++){
       cout<<total[i]<<" ";
       if(total[i]>0){
          count++;
       }
    }
    return count;
}
int main(){
   int arr[] = { 4, 8, 24, 16, 20, 40 };
   int size = sizeof(arr)/sizeof(arr[0]);
   int num = 4;
   cout<<endl<<"Count of occurrences of the average of array elements with a given number are: "<<occurrence_average(arr, size, num);
}

出力結果

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

Count of occurrences of the average of array elements with a given number are:
1 0 0 0 0 0 1

出力行の末尾にある「1」は、関数の戻り値（ゼロ以外の出現回数を持つ要素の個数）が出力されたものです。

補足

平均の計算には整数除算が使われるため、(arr[i] + num) / 2 の結果が小数になる場合は切り捨てられる点に注意してください。また、この実装では std::map を使用しているため、計算量は O(size × log size) となります。パフォーマンスを重視する場合は、std::unordered_map に置き換えることで、平均的な計算量を O(size) まで改善できます。