โจทย์
การเลือกตั้งสภานักเรียนใช้ระบบเสียงข้างมากแบบง่าย ผู้มีสิทธิ์แต่ละคนเขียนชื่อผู้สมัครได้หนึ่งชื่อ และผู้สมัครที่ได้คะแนนมากที่สุดเป็นผู้ชนะ บัตรที่เขียนชื่อซึ่งไม่อยู่ในรายชื่อผู้สมัคร (สะกดผิดหรือเขียนชื่อคนอื่นเพิ่มเอง) ถือเป็นบัตรเสีย ถ้ามีผู้สมัครหลายคนได้คะแนนสูงสุดเท่ากัน ทุกคนจะชนะและดำรงตำแหน่งร่วมกัน
จงเขียน plurality_election(candidates, votes)
อินพุต
candidates: ชื่อผู้สมัคร ซึ่งไม่ซ้ำกันเลย
votes: ชื่อที่ผู้มีสิทธิ์แต่ละคนเขียน คนละหนึ่งชื่อ ชื่อต้องตรงกันทุกตัวอักษร รวมถึงตัวพิมพ์เล็กใหญ่
เอาต์พุต
คืนค่าชื่อผู้ชนะทุกคน เรียงตามลำดับที่ปรากฏใน candidates ถ้าไม่มีบัตรดีเลย ผู้สมัครทุกคนจะเสมอกันที่ 0 คะแนน และต้องคืนค่าทุกคน
เงื่อนไข
1 ≤ ความยาวของ candidates ≤ 20
0 ≤ ความยาวของ votes ≤ 1000
ชื่อประกอบด้วยตัวอักษร ASCII 1 ถึง 20 ตัว
ตัวอย่าง
อินพุต:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Ben", "Ava", "Ben", "Cruz", "Ben"]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ben"]
อินพุต:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Ben", "Ava", "Ben", "Cruz", "Ben"};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ben"};
อินพุต:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Ben", "Ava", "Ben", "Cruz", "Ben"};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ben"};
คำอธิบาย
Ben ได้ 3 คะแนน มากกว่า Ava และ Cruz ที่ได้คนละ 1 คะแนน จึงได้ ["Ben"]
อินพุต:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Cruz", "Ava", "ava", "Dana"]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ava", "Cruz"]
อินพุต:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Cruz", "Ava", "ava", "Dana"};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ava", "Cruz"};
อินพุต:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Cruz", "Ava", "ava", "Dana"};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ava", "Cruz"};
คำอธิบาย
ava และ Dana เป็นบัตรเสีย เหลือ Ava กับ Cruz เสมอกันที่ 1 คะแนน จึงได้ ["Ava", "Cruz"]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ให้ผู้สมัครทุกคนเริ่มที่ 0 คะแนน เพื่อให้ผู้สมัครที่ไม่ได้คะแนนเลยยังถูกนับอยู่
คำใบ้ 2
นับคะแนนเฉพาะเมื่อชื่อตรงกับผู้สมัครทุกตัวอักษร
คำใบ้ 3
หาคะแนนสูงสุดก่อน แล้วรวบรวมทุกคนที่ได้คะแนนนั้นตามลำดับในลิสต์
ความซับซ้อนที่คาดหวัง
เวลา O(c + v), หน่วยความจำเพิ่ม O(c)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน