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

Đế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 đó:

1. a[0] = 0
2. a[1] = 2
3. a[2] = 2
4. 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!