C++で指定範囲内の最小値要素の出現回数をカウントする方法

サイズNの整数型配列が与えられます。変数LとRは、1以上N以下の範囲(L ≥ 1、R ≤ N)を定義します。この記事の目的は、範囲[L, R]内に存在する要素のうち、その範囲での最小値と同じ値を持つ要素がいくつあるかを求めることです。

解決のアプローチ

• まず、範囲L〜R内の要素を走査して最小値を求めます。
• 次に、同じ範囲を再度走査し、手順1で求めた最小値と等しい要素が見つかるたびにカウントを1ずつ増やします。

具体例で確認してみましょう。

例1

入力: arr[] = { 1,2,3,0,3,2,0,1 }、N=8、L=2、R=5
出力: 範囲内の最小値の出現回数 − 1

説明: 範囲L(2)からR(5)に対応する要素はarr[1]〜arr[4]、すなわち { 2,3,0,3 } です。最小値は0であり、その出現回数は1回です。

例2

入力: arr[] = { 1,2,3,0,3,2,0,1 }、N=8、L=3、R=8
出力: 範囲内の最小値の出現回数 − 2

説明: 範囲L(3)からR(8)に対応する要素はarr[2]〜arr[7]、すなわち { 3,0,3,2,0,1 } です。最小値は0であり、その出現回数は2回です。

プログラムで使用しているアルゴリズム

• ランダムな値で初期化した整数型配列arr[]を用意します。
• 整数LとRは配列arr[]内の調査対象範囲を表し、変数countには範囲内の最小値の出現回数が格納されます。
• 関数countSmallest(int arr[], int n, int l, int r)は、配列・その長さ・L・Rを引数として受け取り、指定範囲内の最小値の出現回数を返します。
• 最初に、smallestを範囲の左端の要素arr[l]で初期化し、countは0とします。
• l < 0 かつ r >= n の場合は、無効な範囲が指定されたものとして0を返します。
• インデックスl−1からr−1まで配列を走査し、arr[i]がsmallestより小さければsmallestを更新します。
• 続けて同じ範囲を再度走査し、arr[i]がsmallestと等しければcountをインクリメントします。
• 最後にcountを結果として返します。
• main関数内で、変数countに格納された結果を出力します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
// 指定範囲内の最小値の出現回数を求める関数
int countSmallest(int arr[],int n,int l, int r){
    int smallest=arr[l];
    int count=0;
    if(l<0 && r>=n)
        return 0;
    for(int i=l-1;i<r;i++){
        if(arr[i]<=smallest){
            smallest=arr[i];
        }
    }
    for(int i=l-1;i<r;i++){
        if(arr[i]==smallest){
            ++count;
        }
    }
    return count;
}
int main(){
    int arr[] = { 3,2,1,1,2,3 };
    int n = 6;
    int L,R;
    int count=0;
    L=1,R=5;
    count=countSmallest(arr,n,L,R);
    cout<<endl<<"Count of number of smallest in given range:"<<count;
    L=3,R=4;
    count=countSmallest(arr,n,L,R);
    cout<<endl<<"Count of number of smallest in given range:"<<count;
    return 0;
}

出力

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

Count of number of smallest in given range:2
Count of number of smallest in given range:2

計算量について

この手法では範囲内の要素を2回走査するため、時間計算量はO(R−L+1)、必要な補助メモリはO(1)で済みます。単一のクエリであれば十分に高速ですが、同一の配列に対して多数の範囲クエリを処理する場合は、セグメント木(Segment Tree)やスパーステーブルなどのデータ構造を利用することで、さらに効率的に処理できます。