C++で1つ目の配列にのみ存在し2つ目の配列にはない要素の個数をカウントする方法

問題概要

任意のサイズの整数要素からなる配列が2つ与えられ、「1つ目の配列には存在するが、2つ目の配列には存在しない」要素の個数を求めるのが課題です。

配列とは、同じ型の要素を固定サイズで連続的に格納できるデータ構造の一種です。複数のデータをひとまとめに管理するための基本的な仕組みであり、「同じ型の変数を順番に並べたもの」と考えると理解しやすくなります。

例

入力 − int arr_1[] = {1, 2, 3, 4}
      int arr_2[] = {1, 5, 6, 7, 8}
出力 − カウントは 3

説明 − arr_1 には 1、2、3、4 の要素が含まれ、arr_2 には 1、5、6、7、8 の要素が含まれています。要素 1 は両方の配列に共通して存在するためカウント対象外となり、残る 2、3、4 の 3 個が答えになります。

入力 − int arr_1[] = {10, 20, 30, 40, 50}
      int arr_2[] = {10, 20, 30, 60}
出力 − カウントは 2

説明 − arr_1 には 10、20、30、40、50 が含まれ、arr_2 には 10、20、30、60 が含まれています。10、20、30 は両方の配列に存在するため除外され、残った 40 と 50 の 2 個が答えになります。

プログラムで使用するアルゴリズムの手順

• 2つの配列 arr_1[] と arr_2[] を用意します。
• length() 相当の処理で両方の配列の長さ（要素数）を整数値として取得します。
• 1つ目の配列にのみ存在する要素の個数を格納するための一時変数（カウンタ）を用意します。
• 要素の出現回数を記録するための unordered_map（ここでは up とします）を作成します。
• i を 0 から arr_1 のサイズ未満までループさせます。
• ループ内で up[arr_1[i]] を 1 ずつ増加させ、arr_1 内の各要素の出現回数を記録します。
• 次に i を 0 から arr_2 のサイズ未満までループさせます。
• ループ内で up.find(arr_2[i]) != up.end() かつ up[arr_2[i]] != 0 であるかを判定します。
• 条件を満たす場合は up[arr_2[i]] を 1 減らします。これにより共通要素の分だけ頻度が差し引かれます。
• さらに i を 0 から arr_1 のサイズ未満までループさせます。
• ループ内で up[arr_1[i]] != 0 であるかを判定します。
• 条件を満たす場合はカウントを 1 増やし、二重カウントを防ぐために up[arr_1[i]] を 0 に設定します。
• 最後にカウント値を返します。
• 結果を出力します。

サンプルコード

#include <iostream>
#include<unordered_map>
using namespace std;
int elements_count(int arr_1[], int arr_2[], int m, int n){
    bool f = false;
    int result = 0;
    // 配列 a に含まれる要素の頻度を保存するマップ
    unordered_map<int, int> up;
    for (int i = 0; i < m; i++){
       up[arr_1[i]]++;
    }
    // 配列 b の各要素が a に存在するかどうかを確認
    for (int i = 0; i < n; i++)
    if (up.find(arr_2[i]) != up.end() && up[arr_2[i]] != 0){
       up[arr_2[i]]--;
    }
    // b よりも頻度が多い a の要素をカウント
    for (int i = 0; i < m; i++) {
       if (up[arr_1[i]] != 0){
          result++;
          up[arr_1[i]] = 0;
       }
    }
    return result;
}
// メイン関数
int main(){
    int arr_1[] = { 2, 4, 4, 6, 6, 6, 8, 9 };
    int arr_2[] = { 2, 2, 4, 6, 6 };
    int m = sizeof(arr_1)/sizeof(arr_1[0]);
    int n = sizeof(arr_2)/sizeof(arr_2[0]);
    cout <<"count is "<<elements_count(arr_1, arr_2, m, n);
    return 0;
}

出力

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

count is 4

この例では arr_1 = {2, 4, 4, 6, 6, 6, 8, 9}、arr_2 = {2, 2, 4, 6, 6} です。要素 2 は両方の配列に存在するため除外され、4 は arr_1 に 2 回・arr_2 に 1 回現れるため余分な 1 回がカウントされます。同様に 6 も余分な 1 回がカウントされ、さらに 8 と 9 は arr_2 に存在しないため、合計 4 個という結果になります。なお、このアルゴリズムは重複要素も考慮してカウントする点に注意してください。