Écrivez un code en C++ pour trouver le nombre de sous-tableaux avec les mêmes valeurs minimales et maximales

Dans cet article, nous utiliserons C++ pour résoudre le problème de trouver le nombre de sous-tableaux dont les valeurs maximales et minimales sont les mêmes. Voici un exemple de ce problème −

Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.

Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same.

Comment le résoudre

Par exemple, on peut dire qu'un nombre minimum de sous-tableaux peut être formé en utilisant les mêmes éléments minimum et maximum égaux à la taille du tableau. Le nombre de sous-tableaux peut être plus grand si les nombres consécutifs sont identiques.

Nous pouvons donc utiliser la méthode consistant à parcourir chaque élément et à vérifier si ses nombres consécutifs sont les mêmes. Si les nombres consécutifs sont les mêmes, augmentez le nombre. Si des nombres différents sont trouvés, interrompez la boucle interne.

Chaque fois que la boucle interne se termine ou est interrompue, la variable résultat sera incrémentée et enfin la variable résultat sera affichée.

p>

Exemple

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[ ] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
        int result = n, count =0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if(a[i]==a[j])
                count++;
            else
                break;
        }
        result+=count;
        count =0;
    }
    cout << "Number of subarrays having minimum and maximum elements same:" << result;
    return 0;
}

Sortie

Number of subarrays having minimum and maximum elements same: 9
Time complexity = O(n<sup>2</sup>).

Explication du code ci-dessus

Dans ce code, nous utilisons la variable n pour stocker la taille du tableau, résultat = n, car au moins n sous-tableaux peuvent être formés et le même nombre calculé.

La boucle externe est utilisée pour traiter chaque élément du tableau. La boucle interne est utilisée pour trouver combien de nombres identiques consécutifs il y a après l'élément d'index et à la fin de la boucle interne, elle incrémente la variable de comptage avec la variable de résultat. Enfin, la sortie stockée dans la variable de résultat est affichée.

Méthode efficace

Dans cette méthode, nous parcourons chaque élément et pour chaque élément, nous recherchons combien il y a de mêmes nombres consécutifs. Pour chaque nombre identique trouvé, nous incrémentons la variable de comptage et lorsqu'un nombre différent est trouvé, trouvons combien de sous-tableaux peuvent être formés en utilisant la formule "n = n*(n+1)/2" Incrémentons la variable de résultat.

Exemple

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
        int result = 0;
    int count =1,temp=a[0];
    for (int i = 1; i < n; i++) {
        if (temp==a[i]){
            count++;
        }
        else{
            temp=a[i];
            result = result + (count*(count+1)/2);
            count=1;
        }
    }
    result = result + (count*(count+1)/2);
    cout <<  "Number of subarrays having minimum and maximum elements same:" << result;
    return 0;
}

Sortie

Number of subarrays having minimum and maximum elements same: 9
Time complexity : O(n)

Description du code ci-dessus

Dans ce code, nous stockons le 0ème index du tableau dans la variable temporaire et démarrons la boucle à partir de l'index 1. Nous vérifions si la variable temp est égale à l'élément à l'index actuel et incrémentons le compte de 1 pour le même nombre trouvé. Si la variable temp n'est pas égale à l'élément index, nous trouvons la combinaison de sous-tableaux qui peut être dérivée en comptant le même nombre et stockons le résultat dans la variable result. Nous modifions la valeur temporaire par l'index actuel, réinitialisant le compte à 1. Enfin, nous affichons la réponse stockée dans la variable résultat.

Conclusion

Dans cet article, nous avons résolu le problème de trouver le nombre de sous-tableaux dont les éléments minimum et maximum sont les mêmes. Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. J'espère que cet article vous sera utile.

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!