Problem
Die Wahl zur Schülervertretung ist eine einfache Mehrheitswahl: Jeder Wähler schreibt den Namen eines Kandidaten auf, und wer die meisten Stimmen bekommt, gewinnt. Eine Stimme für einen Namen, der nicht auf der Kandidatenliste steht (ein Tippfehler oder ein frei eingetragener Name), ist ungültig. Haben mehrere Kandidaten gleich viele Stimmen und liegen damit vorn, gewinnen sie alle und teilen sich das Amt.
Implementiere plurality_election(candidates, votes).
Eingabe
candidates: Die Namen der Kandidaten, alle verschieden.
votes: Ein Name pro Wähler. Die Namen müssen genau übereinstimmen, auch in der Groß- und Kleinschreibung.
Ausgabe
Gib die Namen aller Gewinner in der Reihenfolge zurück, in der sie in candidates stehen. Wurde keine gültige Stimme abgegeben, haben alle Kandidaten gleichauf 0 Stimmen und werden alle zurückgegeben.
Einschränkungen
1 ≤ Länge von candidates ≤ 20
0 ≤ Länge von votes ≤ 1000
Namen bestehen aus 1 bis 20 ASCII-Buchstaben
Beispiele
Eingabe:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Ben", "Ava", "Ben", "Cruz", "Ben"]
Erwartete Ausgabe:
expected = ["Ben"]
Eingabe:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Ben", "Ava", "Ben", "Cruz", "Ben"};
Erwartete Ausgabe:
std::vector<std::string> expected = {"Ben"};
Eingabe:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Ben", "Ava", "Ben", "Cruz", "Ben"};
Erwartete Ausgabe:
string[] expected = new string[] {"Ben"};
Erläuterung
Ben hat 3 Stimmen, mehr als Ava und Cruz mit je 1, also ["Ben"].
Eingabe:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Cruz", "Ava", "ava", "Dana"]
Erwartete Ausgabe:
expected = ["Ava", "Cruz"]
Eingabe:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Cruz", "Ava", "ava", "Dana"};
Erwartete Ausgabe:
std::vector<std::string> expected = {"Ava", "Cruz"};
Eingabe:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Cruz", "Ava", "ava", "Dana"};
Erwartete Ausgabe:
string[] expected = new string[] {"Ava", "Cruz"};
Erläuterung
ava und Dana sind ungültig, damit liegen Ava und Cruz mit je 1 Stimme gleichauf: ["Ava", "Cruz"].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Starte jeden Kandidaten mit 0 Stimmen, damit auch Kandidaten ohne Stimmen mitzählen.
Hinweis 2
Zähle eine Stimme nur, wenn der Name genau einem Kandidaten entspricht.
Hinweis 3
Bestimme zuerst die höchste Stimmenzahl und sammle dann alle mit dieser Zahl in der Reihenfolge der Liste.
Erwartete Komplexität
Zeit O(c + v), zusätzlicher Speicher O(c)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.