Đếm số lần xuất hiện của các phần tử trong mảng là một bài tập lập trình giúp các bạn sinh viên biết được về cấu trúc dữ liệu từ điển. Đây là bài tập đơn giản và có thể có nhiều cách giải quyết khác nhau. Tùy vào dữ liệu của bài toán, chúng ta cần có những phương pháp khác nhau để có được đáp án chính xác.
Hãy cùng Nguyễn Văn Hiếu Blog đi tìm các cách giải khác nhau cho bài toán này nhé. Phía cuối mình sẽ có code cho mỗi cách mà mình trình bày.
Phát biểu bài toán
Cho một mảng 1 chiều có n phần tử. Hãy đếm số lần xuất hiện của từng phần tử trong mảng.
Ví dụ: Với n = 5 và a[] = {1, 2, 3, 1, 2}. Khi đó:
- Số 1 xuất hiện 2 lần
- Số 2 xuất hiện 2 lần
- Số 3 xuất hiện 1 lần
Ý tưởng giải bài toán
Cách 1: Sử dụng chỉ số mảng làm key
Để đếm số lần xuất hiện của các phần tử trong mảng, ta cần lưu ý tới phạm vi giá trị của các phần tử trong mảng.
Nếu đề bài đảm bảo các phần tử trong mảng a[i] >= 0 và a[i] < 1000.000(1000.000 ở đây là ví dụ).
Nếu giá trị thỏa mãn không âm và nằm trong phạm vi có thể khai báo mảng bằng giá trị lớn nhất: Chẳng hạn count[1000000] cho ví dụ trên. Khi đó, ta sẽ dùng chỉ số mảng i để đếm số lần xuất hiện của giá trị i.
Ví dụ: Với n = 5 và a[] = {1, 2, 3, 1, 2}. Khi đó:
a[0] = 0a[1] = 2a[2] = 2a[3] = 1
Cách 2: Sử dụng cấu trúc dữ liệu map trong C++
Với cách này, ta sẽ sử dụng cấu trúc dữ liệu map<key, value> để đếm. Khi đó value sẽ lưu số lần xuất hiện của key. Bạn xem code để hiểu cách triển khai nhé.
Cách 3: Sắp xếp, sau đó đếm
Với cách này bạn tiến hành sắp xếp mảng theo chiều tăng dần.
Code đếm số lần xuất hiện của các phần tử
Cách 1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> using namespace std; const int MAX = 1e6; int cnt[MAX]; int main(){ int n; do{ cout << "\nNhap n = "; cin >> n; }while(n < 1); int a[n]; for(int i = 0; i < n;i++){ do{ cout << "\nNhap a[" << i << "] = "; cin >> a[i]; }while(a[i] < 0); } for(int i = 0;i < MAX; i++) cnt[i] = 0; for(int i = 0; i < n;i++){ cnt[a[i]]++; } for(int i = 0;i < MAX; i++){ if(cnt[i] > 0){ cout << "Gia tri " << i << " xuat hien " << cnt[i] << " lan!\n"; } } } |
Output:
|
1 2 3 4 5 6 7 8 9 |
Nhap n = 5 Nhap a[0] = 1 Nhap a[1] = 2 Nhap a[2] = 2 Nhap a[3] = 1 Nhap a[4] = 3 Gia tri 1 xuat hien 2 lan! Gia tri 2 xuat hien 2 lan! Gia tri 3 xuat hien 1 lan! |
Cách 2:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Lưu ý: Code sử dụng C++11 #include <iostream> #include <map> using namespace std; const int N = 1e6; int a[N]; int main(){ int n; cin >> n; map<int, int> cnt; for(int i = 0; i < n;i++){ cin >> a[i]; } for(int i = 0; i < n;i++){ cnt[a[i]]++; } for(auto it : cnt){ cout << "Gia tri " << it.first << " xuat hien " << it.second << " lan!\n"; } } |
Ouput:
|
1 2 3 4 5 6 |
5 1 1 2 3 4 Gia tri 1 xuat hien 2 lan! Gia tri 2 xuat hien 1 lan! Gia tri 3 xuat hien 1 lan! Gia tri 4 xuat hien 1 lan! |
Cách 3:
Dưới đây mình sử dụng hàm std:::sort trong thư viện algorithm C++.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <algorithm> using namespace std; const int N = 1e6; int a[N]; int main(){ int n; cin >> n; for(int i = 0; i < n;i++){ cin >> a[i]; } sort(a, a + n); int cnt = 1; for(int i = 1; i < n;i++){ if(a[i] == a[i-1]) ++cnt; else{ cout << "\nPhan tu " << a[i-1] << " xuat hien " << cnt << " lan!"; cnt = 1; } } cout << "\nPhan tu " << a[n-1] << " xuat hien " << cnt << " lan!"; } |
Output:
|
1 2 3 4 5 6 |
6 1 2 3 1 2 3 Phan tu 1 xuat hien 2 lan! Phan tu 2 xuat hien 2 lan! Phan tu 3 xuat hien 2 lan! |
Chúc các bạn học tốt!
