Pengaturcaraan dalam C++, cari bilangan subarray dengan nombor ganjil m

Jika anda pernah menggunakan C++, anda mesti tahu apa itu subarray dan betapa bergunanya ia. Seperti yang kita semua tahu bahawa dalam C++ kita boleh menyelesaikan pelbagai masalah matematik dengan mudah. Jadi, dalam artikel ini, kami akan menerangkan cara untuk mencari maklumat lengkap nombor ganjil M dengan bantuan subarray ini dalam C++.

Dalam masalah ini, kita perlu mencari beberapa subarray dan integer m yang terdiri daripada tatasusunan yang diberikan, di mana setiap subarray mengandungi tepat m nombor ganjil. Berikut ialah contoh mudah pendekatan ini -

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 }

Pendekatan pertama

Dalam pendekatan ini semua sub-tatasusunan yang mungkin dijana daripada tatasusunan yang diberikan, Dan semak sama ada setiap subarray mempunyai betul-betul m nombor ganjil. Ini ialah kaedah penjanaan dan carian mudah dengan kerumitan masa O(n²).

Contoh

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

Output

Number of subarrays with n numbers are: 6

Penerangan kod di atas

#🎜 kod ini🎜#Bersisipkan kod ini cari subarrays ganjil, gelung luar digunakan untuk menambah "i", yang akan digunakan untuk memproses setiap elemen dalam tatasusunan.

Gelung dalam digunakan untuk mencari subarray dan memproses elemen sehingga pembilang ganjil mencapai m, menambah kiraan pembilang hasil untuk setiap subarray yang ditemui, dan akhirnya mencetak hasil yang disimpan dalam kiraan #🎜🎜 ##🎜 🎜#Kaedah kedua

Kaedah lain ialah mencipta tatasusunan untuk menyimpan bilangan awalan ganjil "i", memproses setiap elemen dan menambah bilangan nombor ganjil setiap kali nombor ganjil dijumpai.

Apabila bilangan nombor ganjil melebihi atau sama dengan m, tambahkan nombor pada kedudukan (ganjil - m) dalam tatasusunan awalan kepadanya.

Apabila nombor ganjil menjadi lebih besar daripada atau sama dengan m, kita mengira bilangan sub-tatasusunan yang terbentuk sehingga indeks dan nombor "ganjil - m" ditambahkan pada pembolehubah kiraan. Selepas setiap elemen diproses, hasilnya disimpan dalam pembolehubah kiraan.

Contoh

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

Output

Number of subarrays with n numbers are: 6

Penerangan kod di atas

#🎜🎜🎜 nilai permulaan # dan initis🎜 -# 🎜🎜#

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

Di sini, kita mulakan pembolehubah n dengan saiz tatasusunan, mulakan pembolehubah m dengan bilangan nombor ganjil yang kita ingin cari, mulakan kiraan dengan 0 untuk mengekalkan kiraan yang mungkin subarrays, mulakan nombor ganjil dengan 0, dan A prefix_array saiz n + 1 memulakan pembolehubah n 0.

Memahami gelung

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

Dalam gelung ini, kami melaksanakan nilai ​​pada indeks ganjil dalam prefix_array[ ], maka Jika nombor ganjil ditemui maka naikkan pembolehubah ganjil. Kami mendapati bahawa apabila pembolehubah ganjil sama dengan atau lebih besar daripada m, bilangan subarray boleh dibentuk, sehingga indeks.

Akhir sekali, kami mencetak nombor subbaris ganjil yang disimpan dalam pembolehubah kiraan dan mendapatkan output.

Kesimpulan

Dalam artikel ini, kami belajar tentang kaedah mencari bilangan subarray m ganjil melalui dua kaedah -

#🎜🎜 #

Hasilkan setiap subarray dan semak sama ada terdapat nombor ganjil di dalamnya, dan tambahkan kiraan setiap subarray yang ditemui. Kerumitan masa kod ini ialah O(n2).

Kaedah yang cekap, lelaran melalui setiap elemen tatasusunan dan cipta tatasusunan awalan, kemudian gunakan bantuan tatasusunan awalan. Kerumitan masa kod ini ialah O(n).
Saya harap artikel ini membantu anda memahami masalah dan penyelesaiannya.

Atas ialah kandungan terperinci Pengaturcaraan dalam C++, cari bilangan subarray dengan nombor ganjil m. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!