【C++】配列内の2つの指定された要素間にある要素数をカウントする方法

はじめに

整数要素を含む配列と、2つの値「start(開始)」と「end(終了)」が与えられたとき、配列内でこの2つの要素の間に存在する要素の個数を求める問題を考えます。本記事では、C++を用いてこの問題を解く具体的な手順を解説します。

配列とは、同じ型の要素を固定サイズで連続的に格納できるデータ構造の一種です。複数のデータをまとめて管理できるため、同じ型の変数の集まりとして考えると理解しやすくなります。

なお、start要素が配列内に複数回出現する場合は最初の出現位置を採用し、end要素が複数回出現する場合は最後の出現位置を採用してカウントするのがポイントです。

具体例

入力: int arr[] = {1, 2, 3, 4, 5, 6, 7}
Start = 1、End = 7
出力: カウントは 5

説明: この配列には7つの要素があり、対象となる範囲は1〜7です。この範囲の間には合計5つの要素が存在します。

入力: int arr[] = {1, 2, 3, 4, 5, 6, 7}
Start = 7、End = 9
出力: カウントは 0

説明: この配列には7つの要素がありますが、範囲7〜9の間に該当する要素が存在しないため、カウントは0になります。

プログラムで使用するアプローチ

• 整数型の配列(int arr[])を入力として受け取ります。
• sizeof演算子などを使って配列のサイズnを求めます。
• ループ変数 i を0から始め、i が配列サイズ未満の間だけ繰り返し、arr[i] == start となった時点でbreakします(先頭からstartを探索)。
• i >= n-1 の場合、startが見つからないか配列の末尾にあるため、0を返します。
• 次に、ループ変数 j を n-1 から始め、j >= i+1 を満たす間 j-- で減少させながら、arr[j] == end となった時点でbreakします(末尾からendを探索)。
• j == i の場合、endが見つからないため、0を返します。
• それ以外の場合は、2つの要素間の個数である j - i - 1 を返します。
• 最後に結果を出力します。

C++による実装例

#include <iostream>
using namespace std;

// 2つの要素間の要素数をカウントする関数
int countelements(int ar[], int n, int start, int end){
    // 先頭からstartを探す
    int i = 0;
    for (i = 0; i < n; i++){
        if (ar[i] == start){
            break;
        }
    }
    // startが存在しない、または末尾にある場合
    if (i >= n-1){
        return 0;
    }
    // 末尾からendを探す
    int j;
    for (j = n-1; j >= i+1; j--){
        if (ar[j] == end){
            break;
        }
    }
    // endが存在しない場合
    if (j == i){
        return 0;
    }
    // 2つの要素間にある要素数を返す
    return (j - i - 1);
}

// メイン関数
int main(){
    int ar[] = { 1, 6, 2, 5, 9, 8, 3, 7, 4 };
    int n = sizeof(ar) / sizeof(ar[0]);
    int start = 5, end = 4;
    cout << "count is " << countelements(ar, n, start, end);
    return 0;
}

出力結果

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

count is 4

説明: 配列 {1, 6, 2, 5, 9, 8, 3, 7, 4} において、start=5 はインデックス3に最初に出現し、end=4 はインデックス8に最後に出現します。その間には {9, 8, 3, 7} の4つの要素が存在するため、答えは4となります。

まとめ

本手法は、startを先頭から、endを末尾からそれぞれ線形探索するシンプルなアプローチです。時間計算量はO(n)、空間計算量はO(1)であり、余分なメモリを使わずに効率よく要素数をカウントできます。startやendが配列に存在しないケースも適切にハンドリングしている点も実務で役立つポイントです。