โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

การเลือกตั้งแบบเสียงข้างมาก

นับคะแนนเสียงคนละหนึ่งเสียง แล้วคืนค่าผู้สมัครทุกคนที่ได้คะแนนมากที่สุด

สิ่งที่คุณจะได้เรียนรู้

  • นับคะแนนของผู้สมัครแต่ละคน
  • ไม่นับคะแนนที่ไม่ถูกต้อง
  • คืนค่าผู้สมัครทุกคนที่ได้คะแนนสูงสุดเท่ากัน

โจทย์

การเลือกตั้งสภานักเรียนใช้ระบบเสียงข้างมากแบบง่าย ผู้มีสิทธิ์แต่ละคนเขียนชื่อผู้สมัครได้หนึ่งชื่อ และผู้สมัครที่ได้คะแนนมากที่สุดเป็นผู้ชนะ บัตรที่เขียนชื่อซึ่งไม่อยู่ในรายชื่อผู้สมัคร (สะกดผิดหรือเขียนชื่อคนอื่นเพิ่มเอง) ถือเป็นบัตรเสีย ถ้ามีผู้สมัครหลายคนได้คะแนนสูงสุดเท่ากัน ทุกคนจะชนะและดำรงตำแหน่งร่วมกัน

จงเขียน plurality_election(candidates, votes)

อินพุต

candidates: ชื่อผู้สมัคร ซึ่งไม่ซ้ำกันเลย

votes: ชื่อที่ผู้มีสิทธิ์แต่ละคนเขียน คนละหนึ่งชื่อ ชื่อต้องตรงกันทุกตัวอักษร รวมถึงตัวพิมพ์เล็กใหญ่

เอาต์พุต

คืนค่าชื่อผู้ชนะทุกคน เรียงตามลำดับที่ปรากฏใน candidates ถ้าไม่มีบัตรดีเลย ผู้สมัครทุกคนจะเสมอกันที่ 0 คะแนน และต้องคืนค่าทุกคน

เงื่อนไข

1 ≤ ความยาวของ candidates ≤ 20

0 ≤ ความยาวของ votes ≤ 1000

ชื่อประกอบด้วยตัวอักษร ASCII 1 ถึง 20 ตัว

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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"]

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก