Đếm số phen xuất hiện tại của những thành phần vô mảng là 1 bài bác tập dượt thiết kế hùn chúng ta SV hiểu rằng về cấu hình tài liệu tự vị. Đây là bài bác tập dượt đơn giản và giản dị và hoàn toàn có thể đem vô số phương pháp xử lý không giống nhau. Tùy vô tài liệu của câu hỏi, tất cả chúng ta cần phải có những cách thức không giống nhau để sở hữu được đáp án đúng mực.
Bạn đang xem: đếm số lần xuất hiện của các phần tử trong mảng
Hãy nằm trong Nguyễn Văn Hiếu Blog đi kiếm những cơ hội giải không giống nhau cho tới câu hỏi này nhé. Phía cuối bản thân sẽ sở hữu được code cho từng cơ hội nhưng mà bản thân trình diễn.
Phát biểu bài bác toán
Cho một mảng một chiều đem n thành phần. Hãy điểm số phen xuất hiện tại của từng thành phần vô mảng.
Ví dụ: Với n = 5
và a[] = {1, 2, 3, 1, 2}
. Khi đó:
- Số 1 xuất hiện tại 2 lần
- Số 2 xuất hiện tại 2 lần
- Số 3 xuất hiện tại 1 lần
Ý tưởng giải bài bác toán
Cách 1: Sử dụng chỉ số mảng thực hiện key
Để đếm số lần xuất hiện của các phần tử trong mảng, tao cần thiết Note cho tới phạm vi độ quý hiếm của những thành phần vô mảng.
Nếu đề bài bác đáp ứng những thành phần vô mảng a[i] >= 0
và a[i] < 1000.000
(1000.000 ở đó là ví dụ).
Nếu độ quý hiếm thỏa mãn nhu cầu ko âm và trực thuộc phạm vi hoàn toàn có thể khai báo mảng bởi vì độ quý hiếm rộng lớn nhất: Chẳng hạn count[1000000]
cho ví dụ bên trên. Khi cơ, tao tiếp tục người sử dụng chỉ số mảng i
để điểm số phen xuất hiện tại của độ quý hiếm i
.
Ví dụ: Với n = 5
và a[] = {1, 2, 3, 1, 2}
. Khi đó:
a[0] = 0
a[1] = 2
a[2] = 2
a[3] = 1
Cách 2: Sử dụng cấu hình tài liệu map
trong C++
Xem thêm: soạn bài luyện tập cách viết đơn và sửa lỗi
Với phương pháp này, tao tiếp tục dùng cấu hình tài liệu map<key, value>
để điểm. Khi cơ value
sẽ lưu số phen xuất hiện tại của key
. Quý khách hàng coi code nhằm hiểu cơ hội xây dựng nhé.
Cách 3: Sắp xếp, tiếp sau đó đếm
Với phương pháp này các bạn tổ chức bố trí mảng theo hướng tăng dần dần.
Cách 1:
#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:
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:
// Lưu ý: Code 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:
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:
Xem thêm: đề thi học kì 2 lớp 10 môn toán có đáp án
Dưới phía trên bản thân dùng hàm std:::sort
vô tủ sách algorithm C++.
#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:
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 chúng ta học tập tốt!
Bình luận