Mảng, xâu & cấu trúc dữ liệu cơ bản

4. Bảng tần suất — kỹ thuật cực hay dùng

Khi cần đếm mỗi giá trị xuất hiện bao nhiêu lần, ta dùng một mảng đếm: cnt[v] lưu số lần giá trị v xuất hiện. Mỗi khi gặp giá trị v, tăng cnt[v] lên 1. Hình minh hoạ bảng tần suất lớn dần khi quét qua dãy:

Bảng tần suất lớn dần. Quét qua dãy 1 3 1 2 3 1; mỗi phần tử làm cột cnt[giá trị] cao thêm một bậc. Kết quả: số 1 xuất hiện 3 lần, số 2 một lần, số 3 hai lần.

Đếm tần suất và tìm số xuất hiện nhiều nhất

tan-suat.cpp

int cnt[1001] = {0};            // gia tri trong khoang 0..1000
for (int i = 0; i < n; i++) {
    cnt[a[i]]++;               // gap a[i] thi tang dem
}
int best = 0;
for (int v = 0; v <= 1000; v++) {
    if (cnt[v] > cnt[best]) best = v;
}
cout << best << " xuat hien " << cnt[best] << " lan\n";

Mẹo: cùng kỹ thuật này đếm tần suất ký tự bằng cnt[s[i]] (mỗi ký tự là một số 0–255).