C++で配列内の異常値（アノマリー）の個数を求める方法

このチュートリアルでは、与えられた配列の中に「異常値」がいくつ含まれているかを求めるプログラムをC++で作成します。

ここで「異常値」とは、ある数と配列内の他のすべての数との絶対差が、指定された値 k よりも大きい場合に該当する数のことです。具体的な例を見てみましょう。

入力例

arr = [3, 1, 5, 7]
k = 1

出力例

4

この例では、配列内のすべての数について、それ以外の数との絶対差が k = 1 より大きいため、4つすべてが異常値としてカウントされます。

アルゴリズム

異常値の個数を求める手順は以下の通りです。

• 配列を初期化します。

• 配列の各要素について、次の処理を繰り返します。

  • 注目している要素以外のすべての要素に対して、絶対差を計算します。

  • 絶対差が k 以下になる組み合わせがひとつでも存在した場合、その要素は異常値ではありません。

  • どの要素とも絶対差が k 以下にならなかった場合のみ、異常値のカウントを1増やします。

C++での実装

上記のアルゴリズムをC++で実装したものが次のコードです。

#include <bits/stdc++.h>
using namespace std;

int getAnomaliesCount(int arr[], int n, int k) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < n; j++) {
            if (i != j && abs(arr[i] - arr[j]) <= k) {
                break;
            }
        }
        if (j == n) {
            count++;
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 1, 5, 7}, k = 1;
    int n = 4;
    cout << getAnomaliesCount(arr, n, k) << endl;
    return 0;
}

実行結果

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

4

計算量について

この実装では、各要素に対して配列全体を走査するため、時間計算量は O(n²) となります。配列のサイズが大きい場合は、配列をソートしてから二分探索や隣接要素との比較を利用することで、O(n log n) まで効率化できる点も覚えておくとよいでしょう。