Mảng đánh dấu và đếm tần suất

Mức độ: Cơ bản

Đề cho dãy 10⁵ số, mỗi số không quá 10⁶, hỏi có hai số nào bằng nhau không. So từng cặp thì có khoảng 5 × 10⁹ cặp. Mảng đánh dấu dùng chính giá trị của số làm chỉ số trong mảng: gặp số x thì xem ô da_gap[x] đã được đánh dấu chưa. Mỗi số chỉ mất một bước, cả dãy chỉ 10⁵ bước.

Mảng đánh dấu

Tạo mảng da_gap gồm 10⁶ + 1 ô, ban đầu toàn False. Đi lần lượt qua dãy:

nếu da_gap[x] đang là True thì x đã xuất hiện trước đó: có số trùng;
ngược lại đánh dấu da_gap[x] = True.

Dãy 4 7 2 7 5:

Số đang xét	da_gap[số] trước khi xét	Việc làm
4	False	đánh dấu 4
7	False	đánh dấu 7
2	False	đánh dấu 2
7	True	có số trùng

Python
C++

import sys
du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])
a = list(map(int, du_lieu[1:1 + n]))   # 0 ≤ a[i] ≤ 10^6
da_gap = [False] * (10 ** 6 + 1)
co_trung = False
for x in a:
    if da_gap[x]:
        co_trung = True
        break
    da_gap[x] = True
print("YES" if co_trung else "NO")

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<bool> daGap(1000001, false);   // 0 ≤ a[i] ≤ 10^6
    bool coTrung = false;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (daGap[x]) coTrung = true;
        daGap[x] = true;
    }
    cout << (coTrung ? "YES" : "NO") << "\n";
    return 0;
}

Mảng đánh dấu còn trả lời ngay câu hỏi “số nhỏ nhất chưa xuất hiện là số nào”: đánh dấu hết dãy, rồi đi từ 0 lên, ô đầu tiên chưa đánh dấu là đáp số.

Mảng đếm tần suất

Thay vì chỉ đánh dấu có hay không, mảng dem ghi số lần xuất hiện: gặp x thì dem[x] += 1. Từ mảng này trả lời được rất nhiều câu hỏi, mỗi câu chỉ cần nhìn vào vài ô:

Câu hỏi	Cách trả lời
x xuất hiện mấy lần?	`dem[x]`
có bao nhiêu giá trị khác nhau?	số ô có `dem[x]` lớn hơn 0
số nào xuất hiện nhiều lần nhất?	ô có `dem` lớn nhất
có bao nhiêu cặp số bằng nhau?	cộng `dem[x] × (dem[x] - 1) / 2` qua mọi x

Đếm cặp có tổng bằng S cũng làm bằng mảng đếm, không cần sắp xếp. Đi lần lượt qua dãy, với mỗi số x, các số đứng trước ghép được với x là các số bằng S - x, có đúng dem[S - x] số như vậy. Cộng vào đáp số, rồi mới tăng dem[x]. Tăng sau như vậy để x không tự ghép với chính nó.

Dãy 1 4 3 2 3, S = 6:

x	S - x	dem[S - x] lúc đó	Đáp số
1	5	0	0
4	2	0	0
3	3	0	0
2	4	1	1
3	3	1	2

Hai cặp là 4 + 2 và 3 + 3.

Python
C++

import sys
du_lieu = sys.stdin.read().split()
n, s = int(du_lieu[0]), int(du_lieu[1])
a = list(map(int, du_lieu[2:2 + n]))   # 0 ≤ a[i] ≤ 10^6
dem = [0] * (10 ** 6 + 1)
so_cap = 0
for x in a:
    can = s - x
    if 0 <= can <= 10 ** 6:
        so_cap += dem[can]
    dem[x] += 1
print(so_cap)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> dem(1000001, 0);   // 0 ≤ a[i] ≤ 10^6
    long long soCap = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        long long can = s - x;
        if (can >= 0 && can <= 1000000) soCap += dem[can];
        dem[x]++;
    }
    cout << soCap << "\n";
    return 0;
}

Lưu ý: S - x có thể âm hoặc lớn hơn 10⁶, phải kiểm tra trước khi dùng làm chỉ số, nếu không chương trình sẽ đọc ra ngoài mảng.

Sắp xếp đếm

Khi các số nhỏ (ví dụ điểm thi từ 0 đến 10, hoặc giá trị không quá 10⁶), đếm tần suất xong thì đi các giá trị từ nhỏ đến lớn, in mỗi giá trị x đúng dem[x] lần là được dãy tăng dần. Cách này tốn khoảng n + (giá trị lớn nhất) bước, không cần so sánh hai số nào với nhau.

Dãy 3 1 3 0 2 1 3: dem[0] = 1, dem[1] = 2, dem[2] = 1, dem[3] = 3, in ra 0 1 1 2 3 3 3.

Khi nào dùng mảng, khi nào dùng dict hoặc map?

Mảng đánh dấu cần một ô cho mỗi giá trị có thể có. Giá trị tới 10⁶ hay 10⁷ thì mảng vẫn vừa bộ nhớ. Giá trị tới 10⁹ thì mảng cần 10⁹ ô, quá lớn.

Giới hạn giá trị	Nên dùng
không quá khoảng 10⁷, không âm	mảng (nhanh nhất)
có số âm, nhưng trong khoảng nhỏ	mảng, cộng thêm một hằng số để chỉ số không âm
lớn (10⁹, 10¹⁸) hoặc là xâu	`dict`/`set` (Python), `map`/`unordered_map`/`set` (C++)

Với giá trị lớn còn một cách khác là rời rạc hóa: đổi các giá trị về 0, 1, 2, … rồi dùng mảng như bình thường.

Luyện tập

Gồm 22 bài, chia thành 6 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Mảng đánh dấu

Bài 1. Có số trùng không

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶). In ra YES nếu có hai vị trí khác nhau chứa cùng một số, ngược lại in ra NO.

Ví dụ:

Nhập	In ra
`5` `4 7 2 7 5`	`YES`

Kiểm tra: nhập

10
12 5 803 47 1000000 0 66 391 25 4

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Đếm số giá trị khác nhau

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶). In ra số giá trị khác nhau trong dãy.

Ví dụ:

Nhập	In ra
`7` `3 1 3 5 1 3 2`	`4`

Kiểm tra: nhập

12
10 20 10 30 40 20 50 10 60 30 70 20

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Số nhỏ nhất chưa xuất hiện

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁹). In ra số tự nhiên nhỏ nhất (tính cả 0) không có mặt trong dãy.

Ví dụ:

Nhập	In ra
`6` `1 0 4 2 7 1`	`3`

Kiểm tra: nhập

10
5 3 1000000000 0 2 8 1 4 9 6

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Thiếu một số

Dãy gồm n - 1 số khác nhau lấy từ 1, 2, …, n, bị mất đúng một số. Dòng đầu có n (2 ≤ n ≤ 10⁶), dòng thứ hai có n - 1 số. In ra số bị mất.

Ví dụ:

Nhập	In ra
`5` `3 1 5 2`	`4`

Kiểm tra: nhập

10
7 2 9 10 1 4 6 3 8

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Có phải hoán vị

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ 10⁹). In ra YES nếu dãy chứa mỗi số 1, 2, …, n đúng một lần (thứ tự tùy ý), ngược lại in ra NO.

Ví dụ:

Nhập	In ra
`5` `4 1 5 3 2`	`YES`

Kiểm tra: nhập

8
3 8 1 6 2 7 2 5

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Mảng đếm tần suất

Bài 6. Thống kê điểm thi

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n điểm thi là số nguyên từ 0 đến 10. In ra 11 số trên một dòng: số bạn được 0 điểm, 1 điểm, …, 10 điểm.

Ví dụ:

Nhập	In ra
`8` `7 8 7 10 5 8 7 9`	`0 0 0 0 0 1 0 3 2 1 1`

Kiểm tra: nhập

15
6 7 8 4 10 6 9 7 7 3 8 6 0 7 9

Xem đáp số

1 0 0 1 1 0 3 4 2 2 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Sắp xếp đếm

Dòng đầu có n (1 ≤ n ≤ 10⁶), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶). In ra dãy đã sắp xếp tăng dần.

Ví dụ:

Nhập	In ra
`7` `3 1 3 0 2 1 3`	`0 1 1 2 3 3 3`

Kiểm tra: nhập

12
50 7 1000000 7 0 33 999999 50 12 7 0 1

Xem đáp số

0 0 1 7 7 7 12 33 50 50 999999 1000000

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Số xuất hiện nhiều lần nhất

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶). In ra số xuất hiện nhiều lần nhất và số lần xuất hiện của nó. Nếu có nhiều số cùng xuất hiện nhiều lần nhất, in số nhỏ nhất trong chúng.

Ví dụ:

Nhập	In ra
`8` `5 2 5 7 2 9 5 2`	`2 3`

Kiểm tra: nhập

12
40 13 7 13 40 7 99 7 13 40 1 2

Xem đáp số

7 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Số chỉ xuất hiện một lần

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶). In ra, theo thứ tự xuất hiện trong dãy, các số chỉ xuất hiện đúng một lần. Nếu không có số nào thì in ra -1.

Ví dụ:

Nhập	In ra
`7` `4 3 4 8 1 3 6`	`8 1 6`

Kiểm tra: nhập

12
9 2 7 2 5 9 11 0 7 3 5 12

Xem đáp số

11 0 3 12

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Đánh dấu đoạn và bội số

Bài 10. Bóng đèn hành lang

Hành lang có n bóng đèn đánh số 1 đến n, ban đầu đều tắt. Có m lần bật đèn, mỗi lần bật mọi bóng từ l đến r (bóng đang sáng vẫn sáng). Dòng đầu có n, m (1 ≤ n ≤ 10⁶, 1 ≤ m ≤ 10⁵), m dòng sau mỗi dòng có l, r (1 ≤ l ≤ r ≤ n). Tổng các độ dài r - l + 1 không quá 10⁶. In ra số bóng đang sáng.

Ví dụ:

Nhập	In ra
`10 3` `2 4` `3 6` `9 9`	`6`

Kiểm tra: nhập

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Bội số trên bảng

Trên bảng viết các số từ 1 đến n. Lần lượt xóa mọi bội của k số cho trước. Dòng đầu có n, k (1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 10⁵), dòng thứ hai có k số b₁, …, b_k (2 ≤ b_i ≤ n, có thể trùng nhau). In ra số lượng số còn lại trên bảng.

Ví dụ:

Nhập	In ra
`20 2` `4 6`	`13`

Kiểm tra: nhập

100 3
6 10 15

Xem đáp số

74

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Đếm cặp và trả lời nhanh

Bài 12. Cặp có tổng bằng S

Dòng đầu có n, S (1 ≤ n ≤ 10⁵, 0 ≤ S ≤ 2 × 10⁶), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶), chưa sắp xếp, có thể trùng. In ra số cặp vị trí i, j với i đứng trước j và a_i + a_j = S.

Ví dụ:

Nhập	In ra
`5 6` `1 4 3 2 3`	`2`

Kiểm tra: nhập

12 10
5 5 3 7 5 1 9 2 8 0 10 5

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Cặp số bằng nhau

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶). In ra số cặp vị trí i, j với i đứng trước j và a_i = a_j.

Ví dụ:

Nhập	In ra
`6` `3 1 3 3 1 2`	`4`

Kiểm tra: nhập

12
7 7 7 7 2 5 2 9 5 7 9 9

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Cặp có hiệu bằng D

Dòng đầu có n, D (1 ≤ n ≤ 10⁵, 1 ≤ D ≤ 10⁶), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶). In ra số cặp vị trí khác nhau (không kể thứ tự) mà hai số chênh nhau đúng D.

Ví dụ:

Nhập	In ra
`6 2` `1 3 5 3 7 2`	`5`

Kiểm tra: nhập

12 5
10 5 15 0 5 20 10 25 3 8 13 8

Xem đáp số

14

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Hỏi số lần xuất hiện

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁶), dòng thứ ba có q số x₁, …, x_q (0 ≤ x_j ≤ 10⁶). Với mỗi x_j, in ra số lần x_j xuất hiện trong dãy, các kết quả cách nhau một dấu cách.

Ví dụ:

Nhập	In ra
`6 3` `2 5 2 8 2 5` `2 5 7`	`3 2 0`

Kiểm tra: nhập

10 5
9 0 9 4 1000000 9 4 3 0 9
9 4 1000000 5 0

Xem đáp số

4 2 1 0 2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Đoạn đầu đủ bộ

Dòng đầu có n, m (1 ≤ m ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên từ 1 đến m. In ra số k nhỏ nhất sao cho k số đầu tiên của dãy chứa đủ cả m giá trị 1, 2, …, m. Nếu cả dãy cũng không đủ, in ra -1.

Ví dụ:

Nhập	In ra
`8 3` `1 1 2 1 3 2 3 1`	`5`

Kiểm tra: nhập

12 5
2 4 2 1 4 4 5 2 1 3 5 1

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 5. Xâu và chữ cái

Bài 17. Hai xâu đảo chữ

Nhập hai xâu s và t trên hai dòng, gồm chữ cái thường, mỗi xâu dài từ 1 đến 10⁵. In ra YES nếu t là một cách sắp xếp lại các chữ cái của s (mỗi chữ cái xuất hiện cùng số lần trong hai xâu), ngược lại in ra NO.

Ví dụ:

Nhập	In ra
`listen` `silent`	`YES`

Kiểm tra: nhập

bumbiiacademy
academybiimub

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Chữ cái xuất hiện nhiều nhất

Nhập một xâu gồm chữ cái thường (1 ≤ độ dài ≤ 10⁵). In ra chữ cái xuất hiện nhiều lần nhất và số lần xuất hiện. Nếu có nhiều chữ cùng nhiều lần nhất, in chữ đứng trước trong bảng chữ cái.

Ví dụ: nhập bumbiiacademy thì in ra a 2.

Kiểm tra: nhập thequickbrownfoxjumpsoverthelazydog.

Xem đáp số

o 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Ký tự đầu tiên không lặp

Nhập một xâu gồm chữ cái thường (1 ≤ độ dài ≤ 10⁵). In ra vị trí (đánh số từ 1) của ký tự đầu tiên chỉ xuất hiện một lần trong xâu. Nếu không có, in ra -1.

Ví dụ: nhập lollipop thì in ra 5.

Kiểm tra: nhập abacabadabacabae.

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 6. Giá trị lớn: dùng dict, set, map

Bài 20. Giá trị lớn: đếm số khác nhau

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10¹⁸). In ra số giá trị khác nhau.

Ví dụ:

Nhập	In ra
`6` `1000000000000 -5 7 -5 1000000000000 0`	`4`

Kiểm tra: nhập

10
-1 999999999999999999 -1 3 -1000000000000000000 3 42 42 7 999999999999999999

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 21. Số chiếm đa số

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số xuất hiện nhiều hơn n/2 lần, hoặc -1000000001 nếu không có số nào như vậy.

Ví dụ:

Nhập	In ra
`7` `3 9 3 3 -2 3 9`	`3`

Kiểm tra: nhập

10
-7 4 -7 4 4 -7 4 -7 -7 4

Xem đáp số

-1000000001

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 22. Cặp có tổng bằng S, giá trị lớn

Dòng đầu có n, S (1 ≤ n ≤ 10⁵, |S| ≤ 2 × 10⁹), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số cặp vị trí i, j với i đứng trước j và a_i + a_j = S.

Ví dụ:

Nhập	In ra
`6 0` `-3 5 3 -5 3 0`	`3`

Kiểm tra: nhập

10 1000000000
500000000 -1000000000 0 1000000000 500000000 999999999 1 500000000 2000000000 -1000000000

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English