Problème
L'élection des délégués se fait à la majorité relative : chaque électeur écrit le nom d'un candidat, et celui qui obtient le plus de voix l'emporte. Un bulletin portant un nom absent de la liste des candidats (une faute de frappe ou un nom ajouté à la main) est déclaré nul. Si plusieurs candidats sont à égalité en tête, ils gagnent tous et partagent le poste.
Implémentez plurality_election(candidates, votes).
Entrée
candidates : les noms des candidats, tous différents.
votes : un nom par électeur. Les noms doivent correspondre exactement, casse comprise.
Sortie
Renvoyez les noms de tous les gagnants dans l'ordre où ils apparaissent dans candidates. Si aucun bulletin n'est valide, tous les candidats sont à égalité avec 0 voix et ils sont tous renvoyés.
Contraintes
1 ≤ longueur de candidates ≤ 20
0 ≤ longueur de votes ≤ 1000
Les noms comptent de 1 à 20 lettres ASCII
Exemples
Entrée :
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Ben", "Ava", "Ben", "Cruz", "Ben"]
Sortie attendue :
expected = ["Ben"]
Entrée :
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Ben", "Ava", "Ben", "Cruz", "Ben"};
Sortie attendue :
std::vector<std::string> expected = {"Ben"};
Entrée :
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Ben", "Ava", "Ben", "Cruz", "Ben"};
Sortie attendue :
string[] expected = new string[] {"Ben"};
Explication
Ben a 3 voix, plus qu'Ava et Cruz qui en ont 1 chacun, d'où ["Ben"].
Entrée :
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Cruz", "Ava", "ava", "Dana"]
Sortie attendue :
expected = ["Ava", "Cruz"]
Entrée :
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Cruz", "Ava", "ava", "Dana"};
Sortie attendue :
std::vector<std::string> expected = {"Ava", "Cruz"};
Entrée :
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Cruz", "Ava", "ava", "Dana"};
Sortie attendue :
string[] expected = new string[] {"Ava", "Cruz"};
Explication
ava et Dana sont des bulletins nuls ; Ava et Cruz restent à égalité avec 1 voix : ["Ava", "Cruz"].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Initialisez chaque candidat à 0 voix pour que les candidats sans voix comptent quand même.
Indice 2
Ne comptez une voix que si le nom correspond exactement à un candidat.
Indice 3
Trouvez d'abord le score maximal, puis récupérez tous ceux qui l'ont atteint, dans l'ordre de la liste.
Complexité attendue
temps O(c + v), espace supplémentaire O(c)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.