Programmation en C++, trouver le nombre de sous-tableaux avec m nombres impairs

Si vous avez déjà utilisé le C++, vous devez savoir ce que sont les sous-tableaux et à quel point ils sont utiles. Comme nous le savons tous, en C++, nous pouvons résoudre facilement plusieurs problèmes mathématiques. Ainsi, dans cet article, nous expliquerons comment trouver les informations complètes sur M nombres impairs à l'aide de ces sous-tableaux en C++.

Dans ce problème, nous devons trouver un nombre de sous-tableaux et d'entiers m constitués du tableau donné, où chaque sous-tableau contient exactement m nombres impairs. Voici un exemple simple de cette approche -

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 }

Première approche

Dans cette approche, tous les sous-tableaux possibles sont générés à partir du tableau donné et chaque sous-tableau est vérifié s'il contient exactement m nombres impairs. Il s'agit d'une méthode simple de génération et de recherche avec une complexité temporelle de O(n²).

Exemple

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

Sortie

Number of subarrays with n numbers are: 6

Description du code ci-dessus

Dans ce code, nous utilisons des boucles imbriquées pour trouver m sous-tableaux impairs, la boucle externe est utilisée pour incrémenter "i", qui sera utilisé pour traiter chacun élément dans le tableau.

La boucle interne est utilisée pour trouver le sous-tableau et traiter les éléments jusqu'à ce que le compteur impair atteigne m, incrémenter le compteur de résultats pour chaque sous-tableau trouvé et enfin imprimer le résultat stocké dans le compte

Deuxième méthode

Une autre méthode consiste à créez un tableau pour stocker le nombre "i" de préfixes impairs, traitez chaque élément et incrémentez le nombre de nombres impairs chaque fois qu'un nombre impair est trouvé.

Lorsque le nombre de nombres impairs est supérieur ou égal à m, ajoutez-y le nombre à la position (impair - m) dans le tableau de préfixes.

Lorsque le nombre impair devient supérieur ou égal à m, nous comptons le nombre de sous-tableaux formés jusqu'à ce que l'index et le nombre "impair - m" soient ajoutés à la variable de comptage. Une fois chaque élément traité, le résultat est stocké dans la variable count.

Exemple

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

Sortie

Number of subarrays with n numbers are: 6

Explication du code ci-dessus

Initialisation des tableaux et des variables à l'aide des valeurs de départ -

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

Ici, nous initialisons la variable n avec la taille du tableau et la variable m avec le nombre de nombres impairs nous recherchons, initialisons count avec 0 pour garder le nombre de sous-tableaux possibles, initialisons les nombres impairs avec 0, initialisons la variable n avec prefix_array de taille n + 1 0.

Comprendre les boucles

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

Dans cette boucle, nous sommes dans prefix_array [ ] implémente la valeur à un index impair, puis incrémente la variable impaire si un nombre impair est trouvé. Nous constatons que lorsque les variables impaires sont égales ou supérieures à m, le nombre de sous-tableaux peut être formé, jusqu'à l'index.

Enfin, nous imprimons les m nombres de sous-tableaux impairs stockés dans la variable count et obtenons le résultat.

Conclusion

Dans cet article, nous avons vu comment trouver le nombre de m sous-tableaux impairs de deux manières -

• Générez chaque sous-tableau et vérifiez s'il contient m nombres impairs et incrémentez chaque sous-tableau. tableau trouvé Le nombre du tableau. La complexité temporelle de ce code est O(n2).

• De manière efficace, parcourez chaque élément du tableau et créez un tableau de préfixes, puis utilisez l'aide du tableau de préfixes. La complexité temporelle de ce code est O(n).

J'espère que cet article vous aidera à comprendre le problème et la solution.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!