【C++】配列内で最初の出現以降に少なくともK回出現する要素の個数を数える方法

はじめに

このチュートリアルでは、配列内の要素のうち、最初の出現以降に少なくともK回出現する要素の個数を求めるプログラムについて解説します。

問題の概要

整数型の配列と値 k が与えられます。私たちのタスクは、注目している各要素について、その要素より後方に存在する同じ値の出現回数が k 回以上であるような要素をすべて数えることです。

アルゴリズムの考え方

この問題は、以下の手順で効率的に解くことができます。

• map を使用して、すでに処理済みの要素を記録し、同じ要素を二度カウントしないようにします（重複の排除）。
• 各要素について、それ以降の位置にある同じ値の出現回数をカウントします。
• 出現回数が k 以上になった時点で内側のループを抜け、条件を満たす要素として答えを1つ増やします。

C++での実装例

#include <iostream>
#include <map>
using namespace std;
// 条件を満たす要素の個数を返す関数
int calc_count(int n, int arr[], int k){
    int cnt, ans = 0;
    // 重複を避けるためのマップ
    map<int, bool> hash;
    for (int i = 0; i < n; i++) {
        cnt = 0;
        // すでに処理した要素はスキップ
        if (hash[arr[i]] == true)
            continue;
        hash[arr[i]] = true;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] == arr[i])
                cnt++;
            // k個見つかったら探索を終了
            if (cnt >= k)
                break;
        }
        if (cnt >= k)
            ans++;
    }
    return ans;
}
int main(){
    int arr[] = { 1, 2, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 1;
    cout << calc_count(n, arr, k);
    return 0;
}

実行結果

1

コードの解説

上記の例では、配列 {1, 2, 1, 3} と k = 1 を関数に渡しています。各要素の判定結果は次のとおりです。

• 要素 1: 最初の出現（インデックス0）以降にもう一度 1 が出現するため、条件を満たします。
• 要素 2: 以降に 2 は出現しないため、条件を満たしません。
• 要素 3: 以降に 3 は出現しないため、条件を満たしません。

したがって、条件を満たす要素は 1 のみとなり、出力は 1 になります。

計算量について

この実装では、外側のループと内側のループの組み合わせにより、最悪の場合 O(n²) の時間計算量となります。ただし、内側のループは k 個見つかった時点で早期に終了するため、実際の処理時間はこれより短くなるケースが多いです。また、map へのアクセスには O(log n) のコストがかかりますが、これによって重複チェックを効率的に行える点がポイントです。