Выборы в школьный совет проходят по простой системе относительного большинства: каждый избиратель пишет имя одного кандидата, и побеждает тот, кто набрал больше всех голосов. Голос за имя, которого нет в списке кандидатов (опечатка или вписанный от руки человек), не засчитывается. Если наибольшее число голосов набрали сразу несколько кандидатов, побеждают все они и делят должность.
Реализуйте plurality_election(candidates, votes).
Входные данные
candidates: имена кандидатов, все различны.
votes: по одному имени от каждого избирателя. Имена должны совпадать точно, с учётом регистра.
Выходные данные
Верните имена всех победителей в том порядке, в котором они идут в candidates. Если ни одного действительного голоса нет, у всех кандидатов поровну, по 0 голосов, и вернуть нужно всех.
Ограничения
1 ≤ длина candidates ≤ 20
0 ≤ длина votes ≤ 1000
Имена состоят из 1-20 букв ASCII
Примеры
Ввод:
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. Следуйте условию и ограничениям выше.