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.

解決方法

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

そこで、各要素を走査し、連続する番号が同じかどうかをチェックする方法を使用できます。連続した番号が同じ場合はカウントが増加し、異なる番号が見つかった場合は、内側のループが実行されます。中断される。

内部ループが終了するか中断されるたびに、結果変数がインクリメントされ、最終的に結果変数が表示されます。

p>

Example

#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;
}

Output

Number of subarrays having minimum and maximum elements same: 9
Time complexity = O(n<sup>2</sup>).

上記のコードの説明

このコードでは、変数 n を使用して、配列 のサイズ、結果 = n。これは、少なくとも n 個の部分配列を形成でき、同じ数のカウントが計算されるためです。

外側のループは、配列内の各要素を処理するために使用されます。内側のループは、インデックス要素の後に連続する同一の数値がいくつあるかを見つけるために使用され、内側のループの最後で、結果変数とともにカウント変数をインクリメントします。最後に、結果変数に保存された出力が表示されます。

効率的な方法

この方法では、各要素を反復処理し、各要素について、連続する同じ数字がいくつあるかを検索します。見つかった同じ数値ごとに count 変数をインクリメントし、異なる数値が見つかったら、式 "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 ずつ増分します。 temp 変数がインデックス要素と等しくない場合は、同じ数を数えることによって導出できる部分配列の組み合わせを見つけ、結果を結果変数に格納します。一時的な値を現在のインデックスに変更し、カウントを 1 にリセットします。最後に、結果変数に格納されている答えを表示します。

結論

この記事では、同じ最小要素と最大要素を持つ部分配列の数を見つける問題を解決しました。また、この問題を解決する C プログラムと、この問題を解決する完全な方法 (通常かつ効率的) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して、同じ最小値と最大値を持つ部分配列の数を見つけるコードを作成します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。