C++ を使用して、合計が奇数の部分配列の数を見つけるコードを作成します。

サブ配列は、配列の連続した部分です。たとえば、配列 [5, 6, 7, 8] を考えると、(5)、(6)、(7)、(8)、(5、6 など) 10 個の空ではないサブ配列があります。 )、(6、7)、(7、8)、(5、6、7)、(6、7、8)、(5、6、7、8)。

このガイドでは、奇数の合計を持つ部分配列の数を見つけるために C で考えられるすべての情報を説明します。奇数の和の部分配列の数を求めるには、さまざまな方法を使用できます。そのため、ここに簡単な例を示します。 -

Input : array = {9,8,7,6,5}
Output : 9

Explanation :
Sum of subarray -
{9} = 9
{7} = 7
{5} = 5
{9,8} = 17
{8,7} = 15
{7,6} = 13
{6,5} = 11
{8,7,6} = 21
{9,8,7,6,5} = 35

ブルート フォース メソッド

この方法により、単純に次の合計であるかどうかを確認できます。すべてのサブ配列の要素が偶数または奇数である場合、そのサブ配列を拒否し、合計が奇数であるサブ配列をカウントします。このコードの複雑さは O(n²)。

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n=5, temp = 0;
    int a[n-1] = { 9,8,7,6,5 } ; // declaring our array.
    int cnt = 0; // counter variable.
    for(int i = 0; i < n; i++){
        temp = 0; // refreshing our temp sum.
        for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till n-1.
            temp = temp + a[j];
            if( temp % 2 == 1 )
                cnt++;
        }
    }
    cout << "Number of subarrays with odd sum : " << cnt << "\n";
    return 0;
}

出力

Number of subarrays with odd sum : 9

上記のコードの説明

このコードではネストされたループが使用されており、外側のループはインクリメントに使用されます。 I の値、I は配列の先頭からの各値を指します。内側のループは、位置 " i " で始まる部分配列を奇数の合計で見つけるために使用されます。

効率的な方法

この方法では、配列の 0 番目の位置からすべての要素を処理します。現在の要素が奇数の場合は、偶数ごとに奇数カウンタをインクリメントし、偶数カウンタをインクリメントします。奇数が見つかった場合、部分配列に奇数を追加するとパリティが変更されるため、偶数と奇数の値が交換され、最後にカウントが結果に追加されます。各要素を処理しているため、このコードの複雑さは O(n) です。

例

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int odd = 0, even = 0,  result = 0,n=5,i,temp;
    int arr[ n-1 ] = { 9,8,7,6,5}; // initialising the array
     // for loop for processing every element of array
    for ( i = 0 ; i < n ; i ++ )  {
        if ( arr[ i ] % 2 == 0 ) {
            even++;
        } else {
          // swapping even odd values
            temp = even;
            even = odd;
            odd = temp + 1;
        }
        result += odd;
    }
    cout << "Number of subarrays with odd sum : " << result;
}

出力

Number of subarrays with odd sum : 9

上記コードの説明

このコードでは、各要素の偶数/奇数をチェックし、値をインクリメントします。偶数の場合は偶数カウンタを、奇数の場合は奇数カウンタをインクリメントします。さらに、奇数が見つかった場合はパリティ カウンタ値を交換し、そうでない場合はサブ配列のパリティを変更します。次に、各反復後に奇数カウンタの値を結果変数に追加します。

結論

この記事では、合計が奇数のサブ配列に対して Brute から数値強制メソッドを見つけ、合計が奇数の各サブ配列を生成し、カウントをインクリメントする方法を説明しました。このコードの時間計算量は O(n2) です。これを効率的に行う方法は、配列の各要素を反復処理し、見つかった奇数/偶数ごとに奇数/偶数カウンタ変数をインクリメントし、奇数が見つかった場合はカウンタを交換することです。このコードの時間計算量は O( n)。この記事が問題と解決策の理解に役立つことを願っています。

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