Đếm tần suất ký tự
Các bài toán liên quan tới tần suất xuất hiện của các kí tự trong xâu có thể sử dụng mảng đánh dấu để giải
Nếu bạn chưa biết về kỹ thuật này, bạn có thể tham khảo tại đây
Các ký tự đều nằm trong bảng mã ASCII có mã từ 0 tới 255, vì thế để đếm tần suất của kí tự ta sẽ thông qua mã ASCII của nó
Để đếm kí tự ta dùng mảng đếm cnt[] có 256 phần tử. Ví dụ khi gặp kí tự 'a' thì ta sẽ cho cnt['a'] hay cnt[97] tăng thêm 1 đơn vị, vì 'a' có mã ASCII là 97.
Ví dụ 1 : Liệt kê các kí tự xuất hiện trong xâu theo thứ tự từ điển tăng dần
#include "stdio.h" #include "string.h" int main(){ char s[] = "28tech c 28tech c java"; int cnt[256] = {0}; for(int i = 0; i < strlen(s); i++){ cnt[s[i]]++; } for(int i = 0; i < 256; i++){ if(cnt[i] != 0){ printf("%c xuat hien %d lan\n", i, cnt[i]); } } return 0; }
Output :
xuat hien 4 lan 2 xuat hien 2 lan 8 xuat hien 2 lan a xuat hien 2 lan c xuat hien 4 lan e xuat hien 2 lan h xuat hien 2 lan j xuat hien 1 lan t xuat hien 2 lan v xuat hien 1 lan
Ví dụ 2 : Liệt kê các kí tự xuất hiện trong xâu theo thứ tự xuất hiện
#include "stdio.h" #include "string.h" int main(){ char s[] = "28tech c 28tech c java zzz"; int cnt[256] = {0}; for(int i = 0; i < strlen(s); i++){ cnt[s[i]]++; } for(int i = 0; i < strlen(s); i++){ if(cnt[s[i]] != 0){ printf("%c xuat hien %d lan\n", s[i], cnt[s[i]]); cnt[s[i]] = 0; } } return 0; }
Output :
2 xuat hien 2 lan 8 xuat hien 2 lan t xuat hien 2 lan e xuat hien 2 lan c xuat hien 4 lan h xuat hien 2 lan xuat hien 5 lan j xuat hien 1 lan a xuat hien 2 lan v xuat hien 1 lan z xuat hien 3 lan
Video hướng dẫn tần suất xuất hiện của ký tự :
