C++で指定範囲内の隣接する等しい要素の個数を数える方法

問題概要

配列とインデックスの範囲が与えられたとき、その範囲内に含まれる「隣り合っていて値が等しい要素のペア」の総数を求める問題です。一見シンプルですが、配列操作の基礎を確認するのに最適な題材です。

まずは具体例で動きを確認してみましょう。

入力例

arr = [1, 2, 2, 2, 3, 3, 4]
lower = 1
upper = 5

出力例

3

この例では、インデックス1〜5の範囲にある隣接ペア (2, 2)、(2, 2)、(3, 3) の3組が等しいため、答えは 3 になります。

アルゴリズム

解き方は非常にシンプルで、範囲内を一度走査しながら隣接要素を比較していくだけです。

• 配列とインデックス範囲(lower・upper)を用意します。
• lower から upper の直前までループで走査します。
  • 現在の要素 arr[i] と次の要素 arr[i + 1] を比較します。
  • 両者が等しければカウントを1つ増やします。
• ループ終了後、カウントを結果として返します。

C++での実装例

上記のアルゴリズムをC++で実装すると、次のようになります。

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

int getEqualElementsCount(int arr[], int n, int lower, int upper) {
    int count = 0;
    // lower から upper の直前まで走査し、隣接する2要素を比較する
    for (int i = lower; i < upper; i++) {
        if (arr[i] == arr[i + 1]) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int arr[] = { 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5 };
    int n = 15;
    // インデックス1〜14の範囲で隣接する等しい要素のペアを数える
    cout << getEqualElementsCount(arr, 15, 1, 14) << endl;
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

10

この配列では、インデックス1以降に「2」が4つ、「3」が3つ、「4」が4つ、「5」が3つ連続して並んでいます。長さ k の連続区間には必ず k−1 個の等しい隣接ペアが含まれるため、(4−1) + (3−1) + (4−1) + (3−1) = 3 + 2 + 3 + 2 = 10 となり、結果は 10 で正しく一致します。

計算量

• 時間計算量: O(upper − lower) — 範囲内の各要素を1度ずつ比較するだけなので、線形時間で処理が完了します。
• 空間計算量: O(1) — カウンタ変数以外に追加のメモリは不要です。

まとめ

隣接要素の比較は、配列の走査と条件分岐という基本操作を組み合わせただけのシンプルな処理です。実装時は範囲の境界、特に upper の扱い(比較対象のペアがどこまで含まれるか)に注意することで、配列外参照などのバグを防げます。この考え方は、「連続する同じ値の区間の検出」や「ランレングス圧縮の前処理」など、さまざまな場面に応用できる便利なテクニックです。