Cách code đếm số lần xuất hiện của các phần tử trong mảng C/C++

Đế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 về lập trình sẽ giúp các bạn sinh viên rất nhiều trong việc hiểu về cấu trúc của dữ liệu. Tuy là một bài tập đơn giản nhưng có rất nhiều phương pháp để giải dạng bài tập này. Việc lựa chọn phương pháp phụ thuộc vào dữ liệu bài toán đưa ra. Hãy cùng tìm hiểu các cách code bài tập này trong bài viết dưới đây.

Các phương pháp giải bài toán đếm số lần xuất hiện của các phần tử trong mảng

Đề bài: Cho một mảng một chiều gồm n phần tử. Hãy đếm số lần xuất hiện của các phần tử trong mảng với n = 5 và a[] = {1, 2, 3, 1, 2}

Ta thấy, số 1 xuất hiện 2 lần, số 2 xuất hiện 2 lần và số 3 xuất hiện 1 lần.

Phương pháp giải

Phương pháp 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 ý đến phạm vi giá trị của các phần tử trong mảng.

Theo đề bài, ta có các phần tử trong mảng đảm bảo 2 điều kiện: a[i] >= 0 và a[i] < 1000.000

Do giá trị thỏa mãn cả 2 điều kiện trên nên ta có thể dùng chỉ số mảng i để đếm số lần xuất hiện của i. Khi đó:

• a[0] = 0;
• a[1] = 2;
• a[2] = 2;
• a[3] = 1;

Phương pháp 2: Sử dụng cấu trúc dữ liệu map trong C++

Theo phương pháp này, ta sẽ sử dụng cấu trúc dữ liệu map<key, value> để đếm số lần xuất hiện của các phần tử. Giá trị value khi đó sẽ lưu lại số lần xuất hiện của key.

Phương pháp 3: Sắp xếp và đếm

Với cách này, chỉ cần sắp xếp mảng theo chiều tăng dần.

Cách code đếm số lần xuất hiện của các phần tử trong mảng chi tiết

Trong bài viết này, chúng tôi sẽ chỉ ra 3 cách giúp các bạn có thể dễ dàng lập trình bài toán đếm số lần xuất hiện của các phần tử trong mảng

Cách 1

Input:

1. #include <iostream>
2. using namespace std;
4. const int MAX = 1e6;
5. int cnt[MAX];
7. int main(){
8.      int n;
9.      do{
10.   cout << “\nNhap n = “;
11. cin >> n;
12.      }while( < 1);
13.      int a[n];
14.      for(int i = 0; i < n;i++){
15. do{
16.     cout << “\nNhap a[“ << i << “] = “;
17.     cin >> a[i];
18. }while(a[i] < 0);
19.      }
20.      for(int i = 0; i < MAX; i++) cnt[i] = 0;
21.      for(int i = 0; i < ; i++){
22. cnt[a[i]]++;
23.      }
24.      for(int i = 0; i < MAX; i ++){
25. if(cnt[i] > 0){
26.     cout << “ Gia tri “ << i << “ xuat hien “ << cnt[i] << “ lan!\n”;
27. }
28.      }
29. }

Output:

1. Nhap n = 5
2. Nhap a[0] = 1
3. Nhap a[1] = 2
4. Nhap a[2] = 2
5. Nhap a[3] = 1
6. Nhap a[4] = 3
7. Gia tri 1 xuat hien 2 lan!
8. Gia tri 2 xuat hien 2 lan!
9. Gia tri 3 xuat hien 1 lan!

Cách 2: Sử dụng C++

Input:

1. #include <iostream>
2. #include <map>
3. using namespace std;
5. const int N = 1e6;
7. int a[N];
9. int main(){
10.      int n;
11.      cin >> n;
12.      map<int, int> cnt;
13.      for(int i = 0; i < n; i++){
14. cin >> a[i];
15.      }
17.      for(int i = 0; i < n; i++){
18. cnt[a[i]]++;
19.      }
20.      for(auto it : cnt){
21. cout << “Gia tri “ << it.first << “ xuat hien “ << it.second << “ lan!\n”;
22.      }
23. }

Output:

1. 5
2. 1 1 2 3 4
3. Gia tri 1 xuat hien 2 lan!
4. Gia tri 2 xuat hien 1 lan!
5. Gia tri 3 xuat hien 1 lan!
6. Gia tri 4 xuat hien 1 lan!

Cách 3: Sử dụng hàm std:::sort trong thư viện algorithm C++

Input:

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
5. const int N = 1e6;
7. int a[N];
9. int main(){
10.      int n;
11.      cin >> n;
12.      for(int i = 0; i < n; i++){
13. cin >> a[i];
14.      }
16.      sort(a, a + );
17.      int cnt = 1;
18.      for(int i = 1; i < ; i++){
19. if(a[i] == a[i-1]) ++cnt;
20. else{
21.     cout << “\nPhan tu “ << a[i-1] << “ xuat hien “ << cnt << “ lan!”;
22.     cnt =1;
23. }
24.      }
25.      cout << “\nPhan tu “ << a[-1] << “ xuat hien “ << cnt << “ lan! “;
27. }

Output:

1. 6
2. 1 2 3 1 2 3
4. Phan tu 1 xuat hien 2 lan!
5. Phan tu 2 xuat hien 2 lan!
6. Phan tu 3 xuat hien 2 lan!

Bài viết trên đây đã tổng hợp đầy đủ các phương pháp cũng như cách code đếm số lần xuất hiện của các phần tử trong mảng C/C++. Hy vọng bài viết có thể giúp các bạn lập trình một cách dễ dàng hơn. Chúc các bạn thực hành thành công.