Đế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 hiểu rằng 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 khắc phục khác nhau. Tùy vào dữ liệu của bài toán, tất cả chúng ta phải có những phương pháp khác nhau để có được lời giải đúng đắn.
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 một 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: Ví dụ 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 phương pháp này, ta sẽ sử dụng cấu trúc dữ liệu mapvàlt;key, valuevàgt; để đế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 phương pháp 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
30
#include <iostreamvàgt;
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
=
;
i
<
n
;
i
++
)
{
do
{
cout
<
<
“nNhap a[“
<
<
i
<
<
“] = “
;
cin
>
>
a
[
i
]
;
}
while
(
a
[
i
]
<
)
;
}
for
(
int
i
=
;
i
<
MAX
;
i
++
)
cnt
[
i
]
=
;
for
(
int
i
=
;
i
<
n
;
i
++
)
{
cnt
[
a
[
i
]
]
++
;
}
for
(
int
i
=
;
i
<
MAX
;
i
++
)
{
if
(
cnt
[
i
]
>
)
{
cout
<
<
“Gia tri “
<
<
i
<
<
” xuat hien “
<
<
cnt
[
i
]
<
<
” lan!n”
;
}
}
}
Output:
1
2
3
4
5
6
7
8
9
10
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
25
// Lưu ý: Code sử dụng C++11
#include <iostreamvàgt;
#include <mapvàgt;
using
namespace
std
;
const
int
N
=
1e6
;
int
a
[
N
]
;
int
main
(
)
{
int
n
;
cin
>
>
n
;
map
<
int
,
int
>
cnt
;
for
(
int
i
=
;
i
<
n
;
i
++
)
{
cin
>
>
a
[
i
]
;
}
for
(
int
i
=
;
i
<
n
;
i
++
)
{
cnt
[
a
[
i
]
]
++
;
}
for
(
tự động
it
:
cnt
)
{
cout
<
<
“Gia tri “
<
<
it
.
first
<
<
” xuat hien “
<
<
it
.
second
<
<
” lan!n”
;
}
}
Ouput:
1
2
3
4
5
6
7
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
28
#include <iostreamvàgt;
#include <algorithmvàgt;
using
namespace
std
;
const
int
N
=
1e6
;
int
a
[
N
]
;
int
main
(
)
{
int
n
;
cin
>
>
n
;
for
(
int
i
=
;
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
7
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!
