C++でソート済み連続配列内の重複要素の出現回数を効率的に求める方法

本記事では、連続する数値で構成される長さnの配列が与えられたとき、その中で唯一複数回繰り返されている要素が何回出現するかを求める方法を解説します。言い換えれば、配列内で繰り返されている要素の連続する長さ（出現回数）を求めることが目的です。

配列はソートされており、要素が連続した値で並んでいるため、隣接する要素同士を比較するシンプルな線形走査で解決できます。具体的には、配列を i=0 から i<n まで順に走査し、arr[i] == arr[i+1] が成り立つたびにカウントを増やしていきます。最後に、最後の要素分としてカウントを1増やせば、それが繰り返し要素の出現回数となります。

それでは、具体的な例で理解を深めましょう。

入力 − arr[]= { 0,1,2,3,3,3 }, N=6

出力 − 繰り返し要素の出現回数 − 3

説明 − この配列では 3 が3回繰り返されています。

入力 − arr[]= { 1,2,3,4,4,4,4,4,5,6 }, N=10

出力 − 繰り返し要素の出現回数 − 5

説明 − この配列では 4 が5回繰り返されています。

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

• 1つの数値が重複して含まれる連続する数値で初期化された整数配列 arr[] を用意します。

• 変数 len に配列の長さを格納します。

• 関数 findRepeat(int arr[], int n) は、配列とその長さを引数として受け取り、繰り返されている要素の値とその出現回数を表示します。

• カウント用変数 count の初期値を 0 とします。

• インデックス i=0 から i<n まで走査し、arr[i] == arr[i+1] が成り立つ場合に count をインクリメントし、その要素を変数 value に格納します。

• ループ終了後、最後の要素分として count を1増やします。

• 繰り返されている要素を value として表示します。

• 繰り返しの回数を count として表示します。

コード例

#include <bits/stdc++.h>
using namespace std;
void findRepeat(int arr[],int n){
    int count=0; //count of repeated element
    int value=0; //to store repeated element
    for(int i=0;i<n;i++){
        if(arr[i]==arr[i+1]){
            count++;
            value=arr[i];
        }
    }
    count++; //for last element
    cout<<"Repeated Element: "<<value;
    cout<<endl<<"Number of occurrences: "<<count;
}
int main(){
    int Arr[]={ 2,3,4,5,5,5,6,7,8 };
    int len=sizeof(Arr)/sizeof(Arr[0]);
    findRepeat(Arr,len);
    return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます −

Repeated Element: 5
Number of occurrences: 3

このアルゴリズムの計算量は O(n) であり、配列を一度走査するだけで結果が得られるため、非常に効率的です。また、配列がソート済みであることを利用しているため、ハッシュマップなどの追加のデータ構造も不要で、空間計算量は O(1) で済みます。