Tulis kod menggunakan C++ untuk mencari bilangan subarray dengan jumlah ganjil

Subarray ialah bahagian bersebelahan daripada tatasusunan. Sebagai contoh, kami menganggap tatasusunan [5, 6, 7, 8], maka terdapat sepuluh sub-tatasusunan bukan kosong, seperti (5), (6), (7), (8), (5, 6). ), (6, 7), (7,8), (5,6,7), (6,7,8) dan (5,6,7,8).

Dalam panduan ini, kami akan menerangkan semua maklumat yang mungkin untuk mencari bilangan subarray dengan jumlah ganjil dalam C++. Untuk mencari bilangan sub-tatasusunan dengan jumlah ganjil kita boleh menggunakan kaedah yang berbeza jadi berikut ialah contoh mudah -

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

Kaedah brute force

Dengan kaedah ini kita hanya boleh menyemak bahawa jumlah elemen dalam semua sub-tatasusunan ialah Genap atau ganjil, jika genap kita akan menolak sub-tatasusunan dan mengira sub-tatasusunan yang jumlahnya ganjil, ini bukan cara yang cekap kerana kerumitan kod ini ialah O(n²).

Contoh

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

Output

Number of subarrays with odd sum : 9

Perihalan kod di atas

Gelung bersarang digunakan dalam kod ini, di mana gelung luar digunakan untuk menambah nilai I, dan I menunjuk kepada setiap nilai dalam tatasusunan dari awal ; gelung dalam digunakan untuk mencari Subarray dengan jumlah ganjil bermula pada kedudukan " i ".

Kaedah yang cekap

Dalam kaedah ini kita memproses setiap elemen bermula dari kedudukan ke-0 dalam tatasusunan. Jika elemen semasa adalah ganjil, tambahkan pembilang ganjil dan tambahkan pembilang genap untuk setiap nombor genap. Jika kita menjumpai nombor ganjil, nilai Genap dan ganjil ditukar, kerana menambah nombor ganjil pada subarray mengubah paritinya, dan akhirnya kiraan ditambahkan pada hasilnya. Kerumitan kod ini ialah O(n) kerana kami sedang memproses setiap elemen.

Contoh

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

Output

Number of subarrays with odd sum : 9

Penjelasan kod di atas

Dalam kod ini, kami menyemak nombor genap/ganjil setiap elemen dan menambah pembilang genap untuk genap dan pembilang ganjil untuk ganjil. Selain itu, jika nombor ganjil ditemui, kami akan menukar nilai kaunter pariti jika tidak, ia akan menukar pariti subbarray. Kemudian tambahkan nilai pembilang ganjil kepada pembolehubah hasil selepas setiap lelaran.

Kesimpulan

Dalam artikel ini kami menerangkan cara mencari kaedah paksaan nombor daripada Brute untuk subarray dengan jumlah ganjil, jana setiap subarray dengan jumlah ganjil dan tambahkan kiraan. Kerumitan masa kod ini ialah O(n2). Cara yang cekap ialah dengan melelakan setiap elemen tatasusunan dan menambah pembolehubah pembilang ganjil/genap dengan setiap nombor ganjil/genap ditemui, menukar pembilang jika nombor ganjil ditemui kerumitan masa kod ini ialah O(n). Saya harap anda mendapati artikel ini membantu dalam memahami masalah dan penyelesaiannya.

Atas ialah kandungan terperinci Tulis kod menggunakan C++ untuk mencari bilangan subarray dengan jumlah ganjil. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!