C++で絶対差がKを超えない配列の最大要素数をカウントする方法

本記事では、任意のサイズの整数要素からなる配列 arr[] と正整数 k が与えられたとき、互いの絶対差が k 以内に収まる要素を数え上げ、その最大数を求める方法を解説します。

配列とは、同じ型の要素を固定サイズで連続的に格納できるデータ構造の一種です。複数のデータをひとまとめに扱うことができ、同じ型の変数の集合として捉えると、その仕組みをより直感的に理解できます。

入出力例

入力 − int arr[] = {2, 3, 6, 12, 14}, k = 5
出力 − カウント: 3

解説 − 絶対差が k（この例では5）を超えない組み合わせは、(2, 3)、(2, 6)、(3, 6) であり、該当する要素は {2, 3, 6} の3個です。したがって、カウントは3となります。

入力 − int arr[] = {2, 3, 6, 12, 14}, k = 10
出力 − カウント: 4

解説 − k = 10 の場合は、(2, 3)、(2, 6)、(3, 6)、(2, 12)、(3, 12)、(6, 12) の各ペアが成立し、条件を満たす要素は {2, 3, 6, 12} の4個です。最大要素数が4であるため、カウントは4となります。

入力 − int arr[] = {2, 3, 6, 12, 14}, k = 0
出力 − カウント: 0

解説 − 差が0になるペア（同一の値の重複）は存在しないため、カウントは0となります。

プログラムで用いるアプローチ

• 配列 arr[] と正整数 k を用意します。
• length() 関数を使用して配列の長さを計算します。この関数は、配列内の要素数に応じた整数値を返します。
• 要素のカウントを格納するための一時変数を用意します。
• first と last という2つの一時変数を宣言し、0で初期化します。
• sort() メソッドを呼び出して配列を昇順にソートします。引数には配列とそのサイズを渡します。
• i を 0 から配列サイズ未満までループさせます。
• ループ内部では、「j < サイズ かつ arr[j] <= arr[i] + k」が成り立つ間、while 文を繰り返します。
• while 文の中で、count < j - i であるかを判定し、真であれば count を j - i に、first を i に、last を j に更新します。
• カウントを返します。
• 結果を出力します。

この手法は「スライディングウィンドウ法（二ポインタ法）」と呼ばれ、ソート済み配列に対して条件を満たす最大の区間を効率よく特定できます。

コード例

#include <iostream>
#include <algorithm>
using namespace std;
int countmax(int arr[], int size, int K){
    int result = 0;
    int i = 0, j = 0;
    int beg = 0;
    int end = 0;
    // 配列をソートする
    sort(arr, arr + size);
    // 最大要素数を求める
    for (i = 0; i < size; i++) {
       // 条件を満たす範囲内の要素をすべてカウントする
       while (j < size && arr[j] <= arr[i] + K)
          j++;
       if (result < (j - i)) {
          result = (j - i);
          beg = i;
          end = j;
       }
    }
    // 最大カウントを返す
    return result;
}
// main 関数
int main(){
    int arr[] = { 2, 3, 6, 12, 14 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int K = 5;
    cout <<"count is "<<countmax(arr, size, K) << endl;
    return 0;
}

出力

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

count is 3

計算量

時間計算量：O(n log n) ― 配列のソートに O(n log n)、ソート後の走査は O(n)
空間計算量：O(1) ― 追加で必要なメモリは定数のみ