C ++を使用して、最小値と最大値が同じであるサブアレイの数を見つけます

この記事では、C++を使用して最大要素と最小要素が同じであるサブ配列の数を見つける問題を解決します。これが問題の例です-

Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.

Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same.

解決策を見つけるためのアプローチ

例を見ると、最小数のサブ配列は、配列のサイズに等しい同じ最小要素と最大要素で形成できると言えます。同じ連続番号がある場合、サブ配列の数はさらに多くなる可能性があります。

したがって、すべての要素を調べて、その連続する番号が同じかどうかを確認し、連続する番号が同じである場合はカウントをインクリメントし、異なる番号が見つかった場合は内部ループを中断するというアプローチを適用できます。

結果変数は、内側のループが終了または中断するたびに結果変数を増やし、最終的に結果変数からの結果を表示します。

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[ ] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
        int result = n, count =0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if(a[i]==a[j])
                count++;
            else
                break;
        }
        result+=count;
        count =0;
    }
    cout << "Number of subarrays having minimum and maximum elements same:" << result;
    return 0;
}

出力

Number of subarrays having minimum and maximum elements same: 9
Time complexity = O(n2).

上記のコードの説明

このコードでは、変数nを使用して配列のサイズを格納しています。結果=nです。これは、最小n個のサブ配列を作成してカウントし、同じ数のカウントを維持できるためです。

外側のループは、配列内のすべての要素を処理するために使用されます。内側のループは、インデックス要素の後に同じである連続番号の数を見つけ、内側のループが終了するたびに結果変数をカウント変数でインクリメントするために使用されます。最後に、結果変数に格納されている出力を表示します。

効率的なアプローチ

このアプローチでは、すべての要素を調べ、すべての要素について、同じ番号がいくつ連続しているかを検索します。見つかった同じ数ごとに、カウント変数をインクリメントし、異なる数が見つかった場合、カウントの助けを借りて、式 "n =n *（n + 1）を使用して形成できるサブ配列の数を見つけます。 / 2 " そして、この式の答えで結果変数をインクリメントします。

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
        int result = 0;
    int count =1,temp=a[0];
    for (int i = 1; i < n; i++) {
        if (temp==a[i]){
            count++;
        }
        else{
            temp=a[i];
            result = result + (count*(count+1)/2);
            count=1;
        }
    }
    result = result + (count*(count+1)/2);
    cout <<  "Number of subarrays having minimum and maximum elements same:" << result;
    return 0;
}

出力

Number of subarrays having minimum and maximum elements same: 9
Time complexity : O(n)

上記のコードの説明

このコードでは、配列の0番目のインデックスをtemp変数に格納し、インデックス1でループを開始します。temp変数が現在のインデックスの要素と等しいかどうかを確認し、見つかった同じ数に対してカウントを1ずつ増やします。一時変数がインデックス要素と等しくない場合、同じ数のカウントから作成できるサブ配列の組み合わせを見つけ、結果を結果変数に格納します。一時値を現在のインデックスリセットカウントに1に変更します。最後に、結果変数に格納されている回答を表示しています。

結論

この記事では、問題を解決して、最小要素と最大要素が同じであるサブ配列の数を見つけます。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。