โจทย์
In an instant runoff election, every voter ranks all the candidates. The count goes in rounds:
- Each ballot counts as one vote for its highest-ranked candidate who is still in the race.
- If a candidate has more than half of all ballots, that candidate wins.
- Otherwise, if every remaining candidate has the same number of votes, they are all tied and the election ends.
- Otherwise, every remaining candidate with the fewest votes is eliminated (all of them at once if several share the lowest count), and a new round starts.
Implement runoff_election(candidates, ballots).
Input
candidates: The candidates' names. Candidate i is candidates[i].
ballots: One row per voter: the candidate numbers (0-based) from most preferred to least preferred. Each row lists every candidate exactly once.
Output
Return a list with the winner's name, or, if the election ends in a tie, the names of all tied candidates in the order they appear in candidates. With no ballots, all candidates are tied.
เงื่อนไข
1 ≤ length of candidates ≤ 9
0 ≤ number of ballots ≤ 200
ตัวอย่าง
อินพุต:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ana"]
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ana"};
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ana"};
คำอธิบาย
Round 1: Ana 2, Bo 2, Cy 1; nobody has more than 2.5, so Cy is out. Cy's ballot moves to Ana, who wins with 3 of 5: ["Ana"].
อินพุต:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ana", "Bo", "Cy"]
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
คำอธิบาย
Every candidate has 2 first-place votes out of 6, so the three of them are tied: ["Ana", "Bo", "Cy"].
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
Keep a true/false list of who is still in the race and recount from scratch every round.
คำใบ้ 2
A majority means votes × 2 greater than the number of ballots.
คำใบ้ 3
Find the lowest count among remaining candidates only; if everyone remaining has it, the election is a tie.
ความซับซ้อนที่คาดหวัง
O(c^2 × b) time, O(c) extra space
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน