Đế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:
- #include <iostream>
- using namespace std;
- const int MAX = 1e6;
- int cnt[MAX];
- int main(){
- int n;
- do{
- cout << “\nNhap n = “;
- cin >> n;
- }while( < 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 < ; 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:
- 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: Sử dụng C++
Input:
- #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”;
- }
- }
Output:
- 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: Sử dụng hàm std:::sort trong thư viện algorithm C++
Input:
- #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 + );
- int cnt = 1;
- for(int i = 1; i < ; 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[-1] << “ xuat hien “ << cnt << “ lan! “;
- }
Output:
- 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!
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.
Tin cùng chuyên mục:
Tổng hợp 5 mẫu bàn ăn đẹp bằng gỗ tự nhiên được ưa chuộng nhất 2023
Sofa nỉ chữ L HNSOFA giải pháp cho không gian phòng khách
Top 10 dòng sản phẩm dù che nắng đa năng tốt nhất tại Hòa Phát Đạt
Thiết kế website bảo vệ đạt chuẩn Digital Marketing