Français
Français
L'algorithme de vote de Moore est un algorithme efficace qui est principalement utilisé pour trouver des éléments dans un tableau qui apparaissent plus de la moitié des fois. Cet algorithme peut compléter l'identification de la plupart des éléments dans une traversée par le comptage et la mise à jour dynamique des éléments candidats. Cet article utilisera le langage PHP comme exemple pour expliquer les scénarios d'application et les processus de mise en œuvre spécifiques de la méthode de vote de Moore, aidant les lecteurs à comprendre et à maîtriser l'utilisation de cet algorithme.
L'idée principale de la méthode de vote de Moore est de "contrer" l'influence de différents éléments, et les éléments restants sont plus de la moitié de la majorité. L'algorithme maintient deux variables: les éléments et compteurs candidats. Lorsque vous traversez le tableau, si le compteur est nul, définissez l'élément actuel comme élément candidat et réinitialisez le compteur à 1; Si l'élément actuel est égal à l'élément candidat, le compteur est augmenté de un; Sinon, le comptoir est réduit d'un. Une fois la traversée terminée, l'élément candidat est le demandé.
Cet algorithme convient non seulement aux tableaux, mais peut également être largement utilisé dans les scénarios suivants:
L'exemple suivant montre comment mettre en œuvre la méthode de vote de Moore en PHP pour trouver des éléments dans un tableau qui apparaissent plus de la moitié des fois.
Définissez les éléments et les variables de contre-contre-candidats, initialisez au premier élément du tableau et 1:
function findMajorityElement($arr) {
$candidate = $arr[0];
$count = 1;
$len = count($arr);
// Itérer dans le tableau
for ($i = 1; $i < $len; $i++) {
// Le comptoir est0heure，Réinitialiser les éléments des candidats
if ($count == 0) {
$candidate = $arr[$i];
$count = 1;
} else {
// L'élément actuel est le même que l'élément candidat，Comptoir plus1
if ($arr[$i] == $candidate) {
$count++;
} else {
// Différents éléments，Contre-décrément1
$count--;
}
}
}
// Retour des éléments candidats
return $candidate;
}Exemple de tableau et d'appels:
$arr = [1, 2, 2, 2, 3];
// Fonction d'appel pour découvrir la plupart des éléments
$majorityElement = findMajorityElement($arr);
echo "L'élément qui apparaît plus de la moitié du temps est：" . $majorityElement;Après avoir exécuté le programme, le résultat de sortie est "l'élément avec plus de la moitié des occurrences est: 2", indiquant que le numéro 2 explique la majorité du tableau.
La méthode de vote de Moore est un algorithme concis et efficace, qui convient particulièrement pour résoudre le problème de la recherche de la plupart des éléments. En comprenant l'idée de base et la logique de mise en œuvre de l'algorithme, il peut être rapidement appliqué à divers scénarios pratiques tels que le comptage des votes électoraux, les statistiques de données et l'analyse des chaînes. J'espère que ce contenu de cet article peut vous aider à mieux comprendre et utiliser PHP pour mettre en œuvre la méthode de vote de Moore.
