Élément majoritaire avec C ++

Soit n le nombre d'éléments dans un vecteur ou un tableau. L'élément ou le leader majoritaire est l'élément qui se produit plus de la moitié des temps de tous les éléments du vecteur. La moitié de n signifie: si n est 10, alors la moitié du temps est 5. L'élément à la moitié de la position est à l'index 4, pour le comptage d'index basé sur zéro. Le moins entier qui est plus de la moitié de 10 est clairement 6 (correspondant à l'indice 5). Si n est 11, alors la moitié de N est toujours considérée comme 5. C'est le nombre total pris lorsque 11 est divisé par 2. L'indice de la moitié est toujours 4 pour l'indexation zéro. Lorsque n est 11, le moins entier qui est clairement plus que la moitié littérale de 11 est toujours 6 (correspondant à l'indice 5).

Ainsi, la moitié de la longueur (taille) d'un vecteur est le résultat d'une division entière de n par 2. C'est-à-dire que le nombre total du quotient, après avoir divisé par 2, est pris s'il y a ou non un reste.

L'élément ou le leader majoritaire est l'élément qui se produit plus de la moitié des temps de tous les éléments du vecteur ou du tableau. Ce doit être plus que la moitié des fois et pas seulement la moitié des fois. C'est-à-dire que cela doit être plus que n / 2 fois (en prenant le nombre entier résultant). La fonction doit retourner -1, si aucun élément majoritaire n'existe.

Cet article explique comment déterminer l'élément majoritaire pour une complexité temporelle de O (n). C'est-à-dire qu'un maximum de n opérations principales est nécessaire pour obtenir l'élément majoritaire.

Exemples vectoriels

Considérez le vecteur suivant:

vecteur A = 6, 8, 4, 6, 8, 6, 6

L'élément majoritaire (leader) est de 6. Il se produit 4 fois sur 7 fois (éléments).

Considérez le vecteur suivant:

vecteur B = 3, 4, 3, 2, 3, -1, 3, 3

L'élément majoritaire est 3. Il se produit 5 fois sur 8 éléments.

Considérez le vecteur suivant:

vecteur C = 4, 3, 4, 4, 4, 2

L'élément majoritaire est 4. Il se produit 4 fois sur 6 éléments.

Considérez le vecteur suivant:

vecteur D = 5, 4, 7, 1, 7, 2, 3, 7, 8

Il n'y a pas d'élément majoritaire ici. Donc, la fonction doit retourner -1. Il y a neuf éléments ici. Le nombre, 7, se produit trois fois et chacun des autres éléments se produit une fois. Trois ne dépasse pas la moitié. Un élément majoritaire acceptable aurait dû se produire, au moins 5 fois.

Illustration pour l'algorithme pour la complexité temporelle O (n)

À partir des vecteurs suivants, deux éléments différents sont supprimés en même temps.

Considérez à nouveau le vecteur:

vecteur A = 6, 8, 4, 6, 8, 6, 6

L'élément de leader (majoritaire) est 6. Les deux premiers éléments sont différents. Si les deux sont supprimés, l'ensemble restant serait, 4, 6, 8, 6, 6. Dans cet ensemble restant, 6 est toujours le leader: trois fois sur 5 fois. Les deux éléments suivants, 4 et 6 sont différents. S'ils sont supprimés, l'ensemble restant sera 8, 6, 6. Dans l'ensemble restant, 6 est toujours le leader. Les deux éléments suivants, 8 et 6 sont différents. S'ils sont supprimés, l'ensemble restant sera 6. Dans ce dernier ensemble d'un seul élément, 6 est toujours le leader. Il semble donc que deux nombres différents soient supprimés à plusieurs reprises. L'élément final restant serait l'élément majoritaire.

Considérez maintenant le vecteur:

vecteur B = 3, 4, 3, 2, 3, -1, 3, 3

L'élément de leader (majoritaire) est 3. Les deux premiers éléments sont différents. Si les deux sont supprimés, l'ensemble restant serait, 3, 2, 3, -1, 3, 3. Dans cet ensemble restant, 3 est toujours le leader: quatre fois sur six fois. Les deux éléments suivants, 3 et 2 sont différents. S'ils sont supprimés, l'ensemble restant sera 3, -1, 3, 3. Dans l'ensemble restant, 3 est toujours le leader. Les deux éléments suivants, 3 et -1 sont différents. S'ils sont supprimés, l'ensemble restant sera 3, 3. Dans ce dernier ensemble de deux éléments, 3 est toujours le leader. Il semble donc toujours que deux nombres différents soient supprimés à plusieurs reprises. Les mêmes derniers éléments restants seraient l'élément majoritaire.

Considérez ensuite le vecteur:

vecteur C = 4, 3, 4, 4, 4, 2

L'élément de leader (majoritaire) est 4. Les deux premiers éléments sont différents. Si les deux sont supprimés, l'ensemble restant serait, 4, 4, 4, 2. Dans cet ensemble restant, 4 est toujours le leader: trois fois sur quatre fois. Les deux éléments suivants, 4 et 4 sont les mêmes et ils ne doivent pas être supprimés. Cependant, le premier élément ici, et le troisième élément ici, peuvent être considérés pour la suppression. Il arrive que ces deux sont également les mêmes. Pourtant, le premier élément et le quatrième élément peuvent être pris en compte pour la suppression. Ils sont différents, donc ils sont supprimés. Le dernier ensemble restant est 4, 4. Il semble donc toujours que deux nombres différents soient supprimés à plusieurs reprises. La finale restante restante serait l'élément majoritaire.

Considérez alors le vecteur:

vecteur D = 5, 4, 7, 1, 7, 2, 3, 7, 8

Nous savons déjà que ce vecteur n'a pas de leader, bien que 7 se produit trois fois et que le nombre se produit une fois. 7 se produit trois fois sur neuf et cela n'en fait pas un leader. Pourtant, différentes paires peuvent être supprimées à plusieurs reprises pour voir à quoi ressemblerait l'ensemble final restant. Les deux premiers éléments, 5 et 4 sont différents. S'ils sont supprimés, l'ensemble restant serait, 7, 1, 7, 2, 3, 7, 8. Dans cet ensemble restant, 7 est toujours l'élément prédominant. Mais ce n'est pas encore le leader de l'ensemble restant. N'oubliez pas que le leader doit se produire plus de la moitié du nombre de fois. Les deux éléments suivants, 7 et 1 sont différents. S'ils sont supprimés, l'ensemble restant serait 7, 2, 3, 7, 8. 7 est toujours l'élément prédominant, mais ce n'est toujours pas le leader. Les deux éléments suivants, 7 et 2 sont différents. Ils sont supprimés pour avoir l'ensemble, 3, 7, 8. Il n'y a aucun élément prédominant qui reste cette fois et il n'y a pas de leader. Les deux éléments suivants, 3 et 7 sont différents. Lorsqu'ils sont supprimés, l'ensemble restant serait 8.

Pour les trois vecteurs précédents, l'élément final restant ou la finale restante restante est l'élément majoritaire. On sait déjà qu'il n'y a pas d'élément majoritaire (leader) dans ce dernier vecteur. Ainsi, le fait qu'un élément reste enfin ne signifie pas nécessairement que c'est l'élément majoritaire.

Maintenant, considérez le cas où n est un nombre uniforme et chaque élément du vecteur se produit une fois. Dans ce cas, toutes les paires d'éléments seront supprimées et il n'y aura aucun élément rester dans l'ensemble final. De toute évidence, dans ce cas, la fonction doit retourner -1 car il n'y a pas d'élément majoritaire.

Pour le dernier élément restant ou les mêmes éléments finaux finaux ont / doivent être vérifiés si l'élément se produit plus de la moitié du nombre de fois dans le vecteur. Cet élément restant est appelé le candidat.

O (n) Algorithme de complexité temporelle pour l'élément majoritaire

La stratégie consiste à supprimer des paires d'éléments différents, à plusieurs reprises: à partir de la gauche dans le vecteur donné. Si aucun élément ne reste, il n'y a pas d'élément majoritaire et que la fonction doit retourner -1. Si un ou plusieurs des mêmes éléments restent, il faut vérifier si l'élément se produit plus de la moitié des fois dans le vecteur. Cet élément est appelé le candidat. Il devient l'élément majoritaire s'il se produit plus de la moitié du nombre de fois.

Cette vérification peut être effectuée en temps linéaire, en scannant le vecteur de la gauche, et s'arrêter dès que le nombre d'occurrence est juste supérieur à la moitié de la longueur du vecteur. Si tout le vecteur est scanné et que le nombre de fois où le candidat se produit ne dépasse pas la moitié des fois, il n'y a pas d'élément majoritaire (selon la définition).

Stratégie avec C++

Avec C ++, les éléments n'ont pas à être supprimés du vecteur donné. Au lieu de cela, une pile est utilisée. Le premier élément du vecteur est poussé dans le haut de la pile. Si l'élément suivant est différent de l'élément supérieur de la pile, alors l'élément supérieur de la pile est supprimé (éteint); Sinon, ce prochain élément est poussé en haut de la pile (si l'élément supérieur de la pile et cet élément suivant, sont les mêmes). Ce schéma se poursuit pour le reste des éléments.

À la fin du balayage (une passe du vecteur), si aucun élément n'est dans la pile, il n'y a pas d'élément majoritaire. Un ou plusieurs éléments peuvent rester dans la pile. Si plus d'un élément reste dans la pile, alors ces éléments restants doivent être les mêmes. Cet élément est appelé le candidat.

Qu'un ou plusieurs du même élément reste dans la pile, cet élément ou le même élément se produisant plus d'une fois est un élément majoritaire possible. Le vecteur doit être reconstitué pour voir si cet élément se produit plus de la moitié du nombre de fois pour le nombre total d'éléments dans le vecteur. Si cela se produit plus de la moitié des fois, alors cet élément est l'élément majoritaire (leader); Sinon, le vecteur (ou le tableau) n'a pas d'élément majoritaire (la fonction doit retourner -1).

Codage C ++

Chaque fois qu'un vecteur est utilisé dans un programme C ++, le titre du programme doit être quelque chose comme:

#inclure
#inclure
#inclure
Utilisation de Namespace Std;

La bibliothèque Stack doit être incluse. L'espace de noms standard est utilisé. Le vecteur est la liste principale, donc sa bibliothèque est incluse. La bibliothèque iOStream doit toujours être incluse; Il est responsable de l'entrée / sortie. Le nom de la fonction de l'algorithme O (n) est majoritairement. La première moitié du code de fonction est:

Int MajorityElement (vecteur &UN)
int n = a.taille();
int size = 0;
empiler St;
St.push (a [0]);
pour (int i = 1; isi (st.size ()> 0) // Pour éviter, l'erreur de défaut de segmentation (core vidé)
if (a [i] == ST.haut())
St.push (a [i]);

autre
St.populaire(); //si différent


autre
St.push (a [i]); // pousse en haut de la pile si vide

Cela a le premier boucle pour la boucle principale. Avant la boucle for, le premier élément du vecteur est envoyé à la pile (le haut). Cette boucle pour implémente la stratégie C ++ ci-dessus. La deuxième et dernière partie de la fonction majoritaire () est:

int candidat = -1;
si (st.size ()> 0)
candidat = ST.haut();
int leader = -1;
int count = 0;
pour (int i = 0; iif (a [i] == candidat)
Count + = 1;


if (compter> n / 2)
leader = candidat;
leader du retour;

Cela vérifie si le candidat est en fait l'élément majoritaire. Le leader variable est un synonyme de l'élément majoritaire. Le candidat variable est l'élément majoritaire possible. Dès que la valeur du décompte dépasse n / 2, alors le candidat est l'élément majoritaire. Cette partie a la boucle pour vérifie si le vecteur a un élément majoritaire. Les deux parties ci-dessus doivent être jointes pour former une fonction. La fonction renvoie -1, si aucun élément majoritaire n'existe.

Une fonction principale C ++ appropriée, pour le code ci-dessus est:

vecteur v1 = 6, 8, 4, 6, 8, 6, 6;
int ret1 = majoritaire (v1);
couter << ret1 << endl;
vecteur v2 = 3, 4, 3, 2, 3, -1, 3, 3;
int ret2 = majoritaire (v2);
couter << ret2 << endl;
vecteur v3 = 4, 3, 4, 4, 4, 2;
int ret3 = majoritaire (v3);
couter << ret3 << endl;
vecteur v4 = 5, 4, 7, 1, 7, 2, 3, 7, 8;
int ret4 = majorityElement (v4);
couter << ret4 << endl;
retour 0;

Complexité temporelle

Puisqu'il y a deux boucles pour le vecteur scannées deux fois, le lecteur pourrait être tenté de dire que la complexité du temps est, o (n + n). Maintenant, le corps de la première boucle pour être beaucoup plus longue que le corps pour la deuxième boucle pour. Ainsi, le temps pour le deuxième corps à forte boucle à exécuter est beaucoup plus petit que le temps pour que le premier corps en boucle puisse exécuter. En d'autres termes, ce temps pour le deuxième corps est relativement négligeable. Ainsi, la complexité temporelle de l'algorithme ci-dessus est citée comme suit:

Sur)

La complexité du temps est le nombre approximatif d'opérations principales pour la fonction en question.

Conclusion

La stratégie générale pour trouver l'élément majoritaire dans le temps d'O (n) consiste à supprimer des paires d'éléments différents, à plusieurs reprises, à partir de la gauche dans la liste donnée. Si aucun élément ne reste, enfin dans la liste, il n'y a pas d'élément majoritaire et que la fonction doit retourner -1. Si un ou plusieurs du même élément restent, il doit être vérifié si l'élément se produit plus de la moitié des fois dans la liste. Cet élément est appelé le candidat. Si le candidat se produit plus de la moitié des fois, dans la liste donnée, alors le candidat est l'élément majoritaire.

Chrys