Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Integrierte Stichwahl (Instant Runoff)

Werte eine integrierte Stichwahl mit Ranglisten-Stimmzetteln aus und scheide Runde für Runde die schwächsten Kandidaten aus.

Das lernst du

  • Jeden Stimmzettel für die höchste verbliebene Wahl zählen
  • Einen Sieger mit absoluter Mehrheit und einen vollständigen Gleichstand erkennen
  • Alle Kandidaten mit der niedrigsten Stimmenzahl ausscheiden lassen

Problem

Bei einer integrierten Stichwahl bringt jeder Wähler alle Kandidaten in eine Rangfolge. Ausgezählt wird in Runden:

  1. Jeder Stimmzettel zählt als eine Stimme für den Kandidaten, der darauf am höchsten eingestuft ist und noch im Rennen ist.
  2. Hat ein Kandidat mehr als die Hälfte aller Stimmzettel, gewinnt er.
  3. Andernfalls gilt: Haben alle verbliebenen Kandidaten gleich viele Stimmen, liegen sie alle gleichauf und die Wahl endet.
  4. 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

Beispiel 1
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"].

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.