Bài gợi ý: Số lần xuất hiện 2 (bản dễ)

Tóm tắt: Bạn có một dãy gồm \(N\) số nguyên dương. Nhiệm vụ của bạn là liệt kê các số xuất hiện trong dãy theo thứ tự từ bé đến lớn, kèm theo số lần mỗi số xuất hiện.

Giả sử dãy có 9 số: 2 3 1 2 3 4 5 4 3. Số bé nhất là số 1 và số 1 chỉ có đúng 1 lần. Số 2 có 2 lần, số 3 có 3 lần, số 4 có 2 lần, còn số 5 có 1 lần. Kết quả cần in ra lần lượt từng dòng: 1 1, 2 2, 3 3, 4 2, và 5 1.

Nếu với mỗi số, ta lại đi dò từ đầu đến cuối dãy để đếm, ta sẽ phải nhìn lại cả dãy rất nhiều lần. Thay vì dò đi dò lại, ta có thể chuẩn bị sẵn một bảng ghi nhớ hay một mảng đếm, đặt tên là cnt. Lúc đầu, mọi ô trong bảng đều mang số 0. Khi đọc đến mỗi giá trị \(x\), ta chỉ cần tăng ô tương ứng lên một đơn vị bằng lệnh cnt[x] += 1.

Cách làm này gọi là đếm phân phối, tức là gom các số giống nhau vào chung một ô để đếm. Vì các số \(A_i\) trong đề bài không vượt quá \(10^5\), bảng đếm chỉ cần chứa tối đa \(100001\) ô là đủ. Sau khi đọc xong cả dãy, bạn cho một biến \(v\) chạy từ \(1\) lên đến số lớn nhất: hễ thấy cnt[v] > 0 thì in ra giá trị \(v\) cùng số lần cnt[v].

Bài tập tương tự:

• Diff-Query (version 1): Luyện tập xử lý các giá trị khác nhau trên từng đoạn của dãy.
• CSES - Distinct Values Queries | Truy vấn Giá trị Khác nhau: Nâng cao kỹ năng đếm số lượng phần tử phân biệt khi có nhiều câu hỏi.

Bạn chỉ cần tạo mảng đếm cnt, duyệt qua từng phần tử để cập nhật cnt[x] += 1, rồi duyệt \(v\) từ \(1\) đến \(10^5\) và in ra những ô có cnt[v] > 0.