Problem
Bei einer integrierten Stichwahl bringt jeder Wähler alle Kandidaten in eine Rangfolge. Ausgezählt wird in Runden:
- Jeder Stimmzettel zählt als eine Stimme für den Kandidaten, der darauf am höchsten eingestuft ist und noch im Rennen ist.
- Hat ein Kandidat mehr als die Hälfte aller Stimmzettel, gewinnt er.
- Andernfalls gilt: Haben alle verbliebenen Kandidaten gleich viele Stimmen, liegen sie alle gleichauf und die Wahl endet.
- Andernfalls scheidet jeder verbliebene Kandidat mit den wenigsten Stimmen aus (alle auf einmal, wenn mehrere die niedrigste Zahl teilen), und eine neue Runde beginnt.
Implementiere runoff_election(candidates, ballots).
Eingabe
candidates: Die Namen der Kandidaten. Kandidat i ist candidates[i].
ballots: Eine Zeile pro Wähler mit den Nummern der Kandidaten (ab 0 gezählt), vom liebsten bis zum am wenigsten gewünschten. Jede Zeile enthält jeden Kandidaten genau einmal.
Ausgabe
Gib eine Liste mit dem Namen des Gewinners zurück oder, wenn die Wahl unentschieden endet, die Namen aller gleichauf liegenden Kandidaten in der Reihenfolge, in der sie in candidates stehen. Ohne Stimmzettel liegen alle Kandidaten gleichauf.
Einschränkungen
1 ≤ Länge von candidates ≤ 9
0 ≤ Anzahl der Stimmzettel ≤ 200
Beispiele
Eingabe:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
Erwartete Ausgabe:
expected = ["Ana"]
Eingabe:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 2, 1},
{1, 2, 0},
{1, 0, 2},
{2, 0, 1}
};
Erwartete Ausgabe:
std::vector<std::string> expected = {"Ana"};
Eingabe:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 2, 1},
new long[] {1, 2, 0},
new long[] {1, 0, 2},
new long[] {2, 0, 1}
};
Erwartete Ausgabe:
string[] expected = new string[] {"Ana"};
Erläuterung
Runde 1: Ana 2, Bo 2, Cy 1; niemand hat mehr als 2,5, also scheidet Cy aus. Der Stimmzettel von Cy geht an Ana, die mit 3 von 5 gewinnt: ["Ana"].
Eingabe:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
Erwartete Ausgabe:
expected = ["Ana", "Bo", "Cy"]
Eingabe:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 1, 0},
{2, 1, 0}
};
Erwartete Ausgabe:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Eingabe:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 1, 0},
new long[] {2, 1, 0}
};
Erwartete Ausgabe:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
Erläuterung
Jeder Kandidat hat 2 von 6 Erststimmen, also liegen alle drei gleichauf: ["Ana", "Bo", "Cy"].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Führe eine Liste aus true/false, wer noch im Rennen ist, und zähle in jeder Runde komplett neu.
Hinweis 2
Eine absolute Mehrheit bedeutet, dass Stimmen × 2 größer ist als die Anzahl der Stimmzettel.
Hinweis 3
Suche die niedrigste Stimmenzahl nur unter den verbliebenen Kandidaten; haben alle Verbliebenen diese Zahl, endet die Wahl unentschieden.
Erwartete Komplexität
Zeit O(c^2 × b), zusätzlicher Speicher O(c)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.