Mô tả và yêu cầu

III.21 – Số phần tử đạt max
Một cuộc lấy ý kiến thăm dò trên mạng cho thấy rất nhiều người có cùng quan
điểm và cho điểm đánh giá cao về các vấn đề được hỏi.
Hãy xác định số lượng người cùng cho điểm đánh giá cao nhất trong số n phiếu
chọn một cách ngẫu nhiên. Có thể ghi nhận và sắp xếp dữ liệu nhưng sẽ tốn rất
nhiều thời gian và công sức. Để trả lời câu hỏi đã nêu chỉ cần xét qua mọi phiếu,
mỗi phiếu một lần và cũng không cần ghi nhận mọi giá trị đã đọc. Nói một cách
khác, cần xử lý với độ phức tạp O(n).
Dữ liệu: Dòng đầu tiên chứa số nguyên n, dòng thứ i trong n dòng sau chứa một
số nguyên – điểm đánh giá của người thứ i. Danh sách điểm chưa được sắp xếp.
Kết quả: Đưa ra số nguyên k – số phần tử đạt giá trị lớn nhất.

Ví dụ

INPUT                                           OUTPUT
 8                                                 3
 6
 5
 6
 8
 7
 8
 6
 8