C++ でのプログラミング、m 個の奇数を持つ部分配列の数を求める

C を使用したことがある場合は、部分配列とは何か、そしてそれがどれほど役立つかを知っているはずです。誰もが知っているように、C では複数の数学的問題を簡単に解決できます。そこで、この記事では、これらの部分配列を使用して C で M 個の奇数の完全な情報を見つける方法を説明します。

この問題では、指定された配列と整数 m で構成されるサブ配列の数を見つける必要があります。ここで、各サブ配列には正確に m 個の奇数が含まれます。このアプローチの簡単な例を次に示します。

Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }

Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }

最初のアプローチ

このアプローチでは、すべての可能なサブ配列が指定された配列から生成され、各サブ配列がチェックされます。 m の奇数。これは、時間計算量が O(n²) の単純な生成および検索方法です。

例

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0; // n is size of array, m numbers to be find in subarrays,
                              // count is number of subarray with m odd numbers
    for (int i = 0; i < n; i++){ // outer loop to process each element.
        int odd = 0;
        for (int j = i; j < n; j++) {// inner loop to find subarray with m number
            if (a[j] % 2)
                odd++;
            if (odd == m) // if odd numbers become equals to m.
                count++;
        }
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

出力

Number of subarrays with n numbers are: 6

上記のコードの説明

このコードでは、ネストされたループを使用して、m 個の奇数の部分配列 (外側のループ) を見つけます。 「i」をインクリメントするために使用され、配列内の各要素を処理するために使用されます。

内部ループは、サブ配列を検索し、奇数カウンタが m に達するまで要素を処理するために使用され、見つかった各サブ配列の結果カウンタ カウントをインクリメントし、最後に count

Second に格納された結果を出力します。 1 つのアプローチ

もう 1 つのアプローチは、「i」個の奇数プレフィックスを格納する配列を作成し、各要素を処理して、奇数が見つかるたびに奇数の数をインクリメントすることです。

奇数の数が m を超える場合は、プレフィックス配列の (奇数 - m) 位置の数値をそれに加えます。

奇数が m 以上になると、インデックスと「奇数 - m」の数値が count 変数に追加されるまで、形成された部分配列の数をカウントします。各要素が処理された後、結果は count 変数に格納されます。

例

#include <bits/stdc++.h>
using namespace std;
int main (){
    int array[ ] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0, odd = 0, i;
    int prefix_array[n + 1] = { 0 };
    // outer loop to process every element of array
    for (i = 0; i < n; i++){
        prefix_array[odd] = prefix_array[odd] + 1;    // implementing value at odd index in prefix_array[ ]
        // if array element is odd then increment odd variable
        if (array[i] % 2 == 0)
            odd++;
        // if Number of odd element becomes equal or greater than m
        //  then find the number of possible subarrays that can be formed till the index.
        if (odd >= m)
            count += prefix_array[odd - m];
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

出力

Number of subarrays with n numbers are: 6

上記のコードの説明

配列と変数を開始値で初期化する -

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };

ここで、変数 n を配列のサイズで初期化し、m を検索する奇数の数で初期化し、可能性のある部分配列の数を保持するために count を 0 で初期化し、奇数を 0 で初期化し、変数 n 0 を prefix_array で初期化します。サイズ n 1 の .

ループについて

for (i = 0; i < n; i++){
   prefix_array[odd] = prefix_array[odd] + 1;
   if (array[i] % 2 == 0)
      odd++;
      if (odd >= m)
         count += prefix_array[odd - m];
}

このループでは、prefix_array[] の奇数インデックスに値を実装し、奇数が見つかった場合は奇数変数をインクリメントします。奇数変数が m 以上の場合、インデックスまでの数の部分配列を形成できることがわかります。

最後に、count 変数に格納されている m 個の奇数の部分配列番号を出力し、出力を取得します。

結論

この記事では、2 つの方法を通じて m 個の奇数部分配列の数を見つける方法について学びました。

• 各部分を生成する。配列配列を作成し、その中に m 個の奇数があるかどうかを確認し、見つかった各サブ配列のカウントをインクリメントします。このコードの時間計算量は O(n2) です。

• 効率的な方法は、配列の各要素を反復処理してプレフィックス配列を作成し、プレフィックス配列の助けを借ります。このコードの時間計算量は O(n) です。

この記事が問題と解決策の理解に役立つことを願っています。

以上がC++ でのプログラミング、m 個の奇数を持つ部分配列の数を求めるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。