Đề bài
Cuộc bầu cử hội học sinh dùng cách bầu theo đa số tương đối đơn giản: mỗi cử tri ghi tên một ứng viên, ai nhiều phiếu nhất thì thắng. Phiếu ghi tên không có trong danh sách ứng viên (viết sai chính tả hoặc tự ghi thêm tên người khác) sẽ bị loại. Nếu nhiều ứng viên cùng có số phiếu cao nhất, tất cả đều thắng và cùng đảm nhận chức vụ.
Hãy viết plurality_election(candidates, votes).
Đầu vào
candidates: Tên các ứng viên, không trùng nhau.
votes: Mỗi cử tri một tên. Tên phải khớp chính xác, kể cả chữ hoa chữ thường.
Đầu ra
Trả về tên tất cả người thắng theo thứ tự xuất hiện trong candidates. Nếu không có phiếu hợp lệ nào, mọi ứng viên cùng hòa với 0 phiếu và đều được trả về.
Ràng buộc
1 ≤ độ dài candidates ≤ 20
0 ≤ độ dài votes ≤ 1000
Mỗi tên có từ 1 đến 20 chữ cái ASCII
Ví dụ
Đầu vào:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Ben", "Ava", "Ben", "Cruz", "Ben"]
Kết quả mong đợi:
expected = ["Ben"]
Đầu vào:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Ben", "Ava", "Ben", "Cruz", "Ben"};
Kết quả mong đợi:
std::vector<std::string> expected = {"Ben"};
Đầu vào:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Ben", "Ava", "Ben", "Cruz", "Ben"};
Kết quả mong đợi:
string[] expected = new string[] {"Ben"};
Giải thích
Ben có 3 phiếu, nhiều hơn Ava và Cruz (mỗi người 1 phiếu), nên kết quả là ["Ben"].
Đầu vào:
candidates = ["Ava", "Ben", "Cruz"]
votes = ["Cruz", "Ava", "ava", "Dana"]
Kết quả mong đợi:
expected = ["Ava", "Cruz"]
Đầu vào:
std::vector<std::string> candidates = {"Ava", "Ben", "Cruz"};
std::vector<std::string> votes = {"Cruz", "Ava", "ava", "Dana"};
Kết quả mong đợi:
std::vector<std::string> expected = {"Ava", "Cruz"};
Đầu vào:
string[] candidates = new string[] {"Ava", "Ben", "Cruz"};
string[] votes = new string[] {"Cruz", "Ava", "ava", "Dana"};
Kết quả mong đợi:
string[] expected = new string[] {"Ava", "Cruz"};
Giải thích
ava và Dana bị loại, còn lại Ava và Cruz cùng hòa với 1 phiếu: ["Ava", "Cruz"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Khởi tạo mỗi ứng viên với 0 phiếu để ứng viên không có phiếu nào vẫn được tính.
Gợi ý 2
Chỉ đếm một phiếu khi tên trên phiếu trùng khớp chính xác với một ứng viên.
Gợi ý 3
Tìm số phiếu cao nhất trước, rồi gom mọi ứng viên có số phiếu đó theo thứ tự trong danh sách.
Độ phức tạp mong đợi
thời gian O(c + v), bộ nhớ phụ O(c)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.