Tìm kiếm nhị phân 3 (SEARCH3)
Đề bài
SEARCH3 – Tìm kiếm nhị phân 3
Cho hai dãy số nguyên $a_1, a_2, \ldots, a_n$ và $b_1, b_2, \ldots, b_m$. Với mỗi chỉ số $i$ $(1 \le i \le m)$ hãy tìm sự xuất hiện của $b_i$ trong dãy $a_1, a_2, \ldots, a_n$.
Dữ liệu vào:
- Dòng đầu ghi hai số nguyên dương $n$ và $m$;
- Dòng thứ hai ghi $n$ số nguyên $a_1, a_2, \ldots, a_n$;
- Dòng thứ ba ghi $m$ số nguyên $b_1, b_2, \ldots, b_m$.
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Giới hạn: $1 \le n, m \le 10^5$; $|a_i|, |b_i| \le 10^9$.
Dữ liệu ra: Một dòng duy nhất chứa $m$ số nguyên, trong đó số thứ $i$ $(1 \le i \le m)$ là chỉ số $j$ nhỏ nhất mà $a_j = b_i$ (nếu tồn tại) và là $0$ nếu ngược lại. Hai số liên tiếp được ghi cách nhau một dấu cách.
7 5
6 4 7 2 4 1 3
3 1 5 4 87 6 0 2 0Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Trước khi vào bài, các bạn nhớ giúp mình chuyện giới hạn thời gian: với các hệ thống chấm bài giới hạn 1 giây (như bài này), toàn bài chỉ nên lặp cỡ $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất $10^8$ lần (lúc này hên xui). Ngưỡng này là cho C/C++; Python, Java, C# chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân ngưỡng lên 2, 100 ms thì chia 10, cứ thế mà tính.
Giải thích ví dụ cho bạn nào chưa hiểu đề. Dãy $a$ (đánh số từ $1$):
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| aj | 6 | 4 | 7 | 2 | 4 | 1 | 3 |
- $b_1 = 3$: số $3$ nằm ở vị trí $7$ ⇒ in 7.
- $b_2 = 1$: số $1$ nằm ở vị trí $6$ ⇒ in 6.
- $b_3 = 5$: không có trong $a$ ⇒ in 0.
- $b_4 = 4$: số $4$ xuất hiện ở cả vị trí 2 và 5, đề bắt lấy vị trí nhỏ nhất ⇒ in 2. Đây là chỗ "khó chịu" nhất của bài, lát nữa các bạn sẽ thấy.
- $b_5 = 8$: không có ⇒ in 0.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Tìm kiếm tuần tự – O(N·M)
Cách đơn giản nhất dễ dàng nhìn ra là theo tư tưởng vét cạn: với từng giá trị $b_i$, so sánh lần lượt với các giá trị $a_j$ từ trái qua. Ngay tại vị trí $a_j$ nào bằng $b_i$ thì kết luận in ra vị trí $j$ đó luôn (đi từ trái qua nên gặp đầu tiên chắc chắn là vị trí nhỏ nhất) rồi xét qua $b_i$ tiếp theo. Còn xét tới tận cùng mà vẫn không thấy $a_j$ nào bằng $b_i$ thì in ra $0$. Cứ thế xét hết tất cả các giá trị $b_i$.
x, đọc vào, tìm, in kết quả, rồi lại đọc giá trị mới vào, cứ thế.Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
while(m--){
int x;
cin >> x;
int idx = 0;
for(int i = 0; i < n; ++i){
if(a[i] == x){
idx = i + 1;
break;
}
}
cout << idx << " ";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
b = list(map(int, data[2 + n:2 + n + m]))
res = []
for x in b:
idx = 0
for i in range(n):
if a[i] == x:
idx = i + 1
break
res.append(idx)
print(*res)Bấm Tiếp để chạy tay từng dòng code (mảng a ở đây đánh số từ $0$ nên vị trí in ra là i + 1):
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ với $N$ là số phần tử của mảng $a$.
- Thời gian: $O(N)$ đọc mảng $a$ + $O(M \cdot N)$ cho bước đọc từng số của $b$ rồi đi tìm. Theo quy tắc cộng Big-O lấy cái lớn nhất làm đại diện ⇒ $O(M \cdot N)$, với $M$ là số phần tử của $b$, $N$ là số phần tử của $a$.
Cách 2Sắp xếp + lọc trùng + tìm kiếm nhị phân – O(max(N, M)·logN)
Giờ ta nói về cách làm tốt hơn. Thực ra ngay từ chính tên đề bài đã nói rõ cách làm rồi còn gì 😆: ta phải tìm kiếm nhị phân để đẩy nhanh quá trình tìm kiếm, chứ tìm kiếm tuần tự như trên là TLE. Bạn nào chưa biết tìm kiếm nhị phân là gì thì trước tiên phải tìm đọc tài liệu cho hiểu đã nhé, còn bạn nào biết rồi thì xem tiếp. Có hai trở ngại cần xử lý trước khi tìm kiếm nhị phân được.
Trở ngại 1: sắp xếp làm mất vị trí ban đầu
Muốn tìm kiếm nhị phân thì danh sách bắt buộc phải có trật tự (tăng dần hoặc giảm dần), nghĩa là ta phải sắp xếp. Mà sắp xếp xong thì vị trí các phần tử đã bị đổi khác so với ban đầu, trong khi đề lại muốn in ra vị trí theo dãy trước khi sắp xếp.
(value, index) = $(a_j, j)$. Sắp xếp theo value, tìm kiếm nhị phân gặp đúng phần tử thì in ra index mà nó mang theo – tức vị trí $j$ ban đầu – chứ không phải vị trí hiện tại sau khi sắp xếp. Trong C++ mình gom 2 thông tin này vào một struct Data.Trở ngại 2: phần tử trùng nhau
Mảng $a$ có thể có các phần tử trùng nhau. Khi tìm kiếm nhị phân, giả sử tìm ra một $a_j$ bằng $b_i$ thì cũng không đảm bảo $a_j$ đó đang mang theo index nhỏ nhất (vị trí xuất hiện đầu tiên). Thêm nữa, hàm sort của STL không giữ nguyên thứ tự ban đầu của các phần tử bằng nhau, nên ngay cả phần tử đứng đầu nhóm trùng cũng chưa chắc có index nhỏ nhất.
Vậy cần một bước tiền xử lý sau khi sắp xếp: loại bớt các phần tử trùng, chỉ để lại duy nhất 1 phần tử cho mỗi giá trị, và index nó giữ phải là nhỏ nhất trong nhóm. Việc này khá đơn giản vì sau khi sắp xếp thì các phần tử trùng nhau đã nằm sát cạnh nhau, chỉ cần duyệt 1 vòng là xét hết.
Các bạn tưởng tượng ta tạo thêm một mảng c để chứa các phần tử phân biệt lấy ra từ a: xét $a_j$ hiện tại, trùng với phần tử cuối cùng của c thì coi như bị trùng, không lấy; khác thì đưa $a_j$ vào cuối c. Chỉ cần 1 vòng lặp – $O(N)$. Ta chấp nhận tốn thêm bộ nhớ cho c nhưng về mặt thời gian thì tối ưu hơn rất nhiều so với xoá.
a là mảng c. Biến cnt là số phần tử phân biệt đã có (chúng nằm ở a[0..cnt-1], ban đầu cnt = 1), biến i duyệt từ 1:
a[i].valuekháca[cnt-1].value(phần tử cuối của "mảng c") ⇒ giá trị mới:cnt++rồi chépa[i]vàoa[cnt-1].- Trùng nhau ⇒ giữ nguyên
cnt, nhưng nếua[i].indexnhỏ hơn thì cập nhậta[cnt-1].indexđể giá trị đó luôn mang theo vị trí ban đầu nhỏ nhất.
n = cnt – số phần tử phân biệt. Các bạn thử suy ngẫm xem nhé.Ở bước sắp xếp nhớ dùng thuật toán tối ưu $O(N \log N)$ chứ cài mấy thuật $O(N^2)$ (nổi bọt, chọn...) thì vẫn TLE. Đơn giản nhất là gọi hàm sort có sẵn trong STL, kèm hàm so sánh cmp để nó biết so 2 phần tử theo value.
Xử lý xong 2 trở ngại thì phần còn lại quá đơn giản: với mỗi $b_i$, tìm kiếm nhị phân trên mảng $a$ (đã sắp xếp, đã lọc trùng); tìm thấy thì in index mà nó lưu trữ, không thấy thì in $0$.
Em nhập dãy $a$, dãy $b$ nhỏ rồi bấm Tiếp để xem đủ 3 giai đoạn: sắp xếp, lọc trùng bằng 2 con trỏ, rồi tìm kiếm nhị phân cho từng $b_i$:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
struct Data{
int value;
int index;
};
// Hàm so sánh cho sort: so theo value, sắp xếp tăng dần
bool cmp(const Data &a, const Data &b){
return a.value < b.value;
}
int main(){
int n, m;
cin >> n >> m;
Data a[n];
for(int i = 0; i < n; ++i){
cin >> a[i].value;
a[i].index = i + 1;
}
// Sắp xếp tăng dần theo value, O(N * logN)
sort(a, a + n, cmp);
// Lọc phần tử phân biệt ngay trên mảng a (2 con trỏ)
int cnt = 1;
for(int i = 1; i < n; ++i){
if(a[i].value != a[cnt - 1].value){
cnt++;
a[cnt - 1] = a[i];
}
else{
if(a[i].index < a[cnt - 1].index){
a[cnt - 1].index = a[i].index;
}
}
}
n = cnt; // cập nhật lại số phần tử phân biệt
// Tìm kiếm nhị phân
while(m--){
int x;
cin >> x;
int idx = 0;
int left = 0, right = n - 1;
while(left <= right){
int mid = (left + right) / 2;
if(a[mid].value < x){
left = mid + 1;
}
else if(a[mid].value > x){
right = mid - 1;
}
else{
idx = a[mid].index;
break;
}
}
cout << idx << " ";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
b = data[2 + n:2 + n + m]
# mỗi phần tử là [value, index]
a = [[int(data[2 + i]), i + 1] for i in range(n)]
a.sort(key=lambda p: p[0]) # sắp xếp tăng dần theo value
# lọc phần tử phân biệt ngay trên mảng a (2 con trỏ)
cnt = 1
for i in range(1, n):
if a[i][0] != a[cnt - 1][0]:
cnt += 1
a[cnt - 1] = a[i]
elif a[i][1] < a[cnt - 1][1]:
a[cnt - 1][1] = a[i][1]
n = cnt # cập nhật lại số phần tử phân biệt
res = []
for t in b:
x = int(t)
idx = 0
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if a[mid][0] < x:
left = mid + 1
elif a[mid][0] > x:
right = mid - 1
else:
idx = a[mid][1]
break
res.append(idx)
print(*res)Bấm Tiếp để chạy tay từng dòng code (bảng "Dữ liệu" có 2 hàng value / index của mảng a; ô mờ là phần đã bị bỏ sau khi lọc trùng):
Viết gọn hơn với upper_bound
Ở trên ta tự cài đặt tìm kiếm nhị phân. Trong STL cũng có hàm binary_search, nhưng nó chỉ cho biết có tìm thấy hay không, còn ở đây ta cần biết tìm thấy ở ô nào để lấy ra index mà phần tử đó lưu trữ, nên không áp dụng hàm đó được. Muốn lấy được vị trí thì có 2 hàm lower_bound, upper_bound làm được điều này (các bạn Google tìm hiểu thêm về 2 hàm này nhé). Ví dụ mình làm mẫu với upper_bound: nó trả về ô đầu tiên có value lớn hơn x, nên nếu x có trong mảng thì nó nằm ngay ô liền trước, upper - 1.
#include <bits/stdc++.h>
using namespace std;
struct Data{
int value;
int index;
};
// Hàm so sánh cho sort: so theo value, sắp xếp tăng dần
bool cmp(const Data &a, const Data &b){
return a.value < b.value;
}
int main(){
int n, m;
cin >> n >> m;
Data a[n];
for(int i = 0; i < n; ++i){
cin >> a[i].value;
a[i].index = i + 1;
}
sort(a, a + n, cmp);
int cnt = 1;
for(int i = 1; i < n; ++i){
if(a[i].value != a[cnt - 1].value){
cnt++;
a[cnt - 1] = a[i];
}
else{
if(a[i].index < a[cnt - 1].index){
a[cnt - 1].index = a[i].index;
}
}
}
n = cnt;
// Tìm kiếm nhị phân bằng hàm upper_bound
while(m--){
Data x;
cin >> x.value;
int upper = upper_bound(a, a + n, x, cmp) - a;
if(upper == 0 || a[upper - 1].value != x.value){
cout << "0 ";
}
else{
cout << a[upper - 1].index << " ";
}
}
return 0;
}import sys
from bisect import bisect_right
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
b = data[2 + n:2 + n + m]
a = [[int(data[2 + i]), i + 1] for i in range(n)]
a.sort(key=lambda p: p[0])
cnt = 1
for i in range(1, n):
if a[i][0] != a[cnt - 1][0]:
cnt += 1
a[cnt - 1] = a[i]
elif a[i][1] < a[cnt - 1][1]:
a[cnt - 1][1] = a[i][1]
n = cnt
vals = [a[i][0] for i in range(n)] # dãy value phân biệt, tăng dần
res = []
for t in b:
x = int(t)
upper = bisect_right(vals, x) # tương đương upper_bound
if upper == 0 or vals[upper - 1] != x:
res.append(0)
else:
res.append(a[upper - 1][1])
print(*res)upper_bound trả về ô $0$, lúc đó a[upper - 1] chính là a[-1] – truy cập ra ngoài mảng. Trong code gốc mình viết trên điện thoại thiếu kiểm tra này, nên ở đây mình bổ sung thêm điều kiện upper == 0 || phía trước cho chắc ăn nha.Về mặt độ phức tạp thì tự cài tìm kiếm nhị phân hay dùng upper_bound đều như nhau. Tuy nhiên rõ ràng bạn nào biết dùng upper_bound thì code ngắn hơn, hoàn thành bài nhanh hơn – trong cuộc thi có tính thời gian thì đây là lợi thế.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ với $N$ là số phần tử của mảng $a$.
- Thời gian: $O(N)$ đọc mảng $a$ + $O(N \log N)$ sắp xếp + $O(N)$ lọc phần tử phân biệt + $O(M \log N)$ tìm kiếm nhị phân. Theo quy tắc cộng Big-O lấy cái lớn nhất ⇒ $O(\max(N, M) \cdot \log N)$.
Cách 3Dùng map – O((N + M)·logN)
Vẫn còn một cách nữa, độ phức tạp cỡ tương tự cách 2 nhưng code rất gọn: dùng cấu trúc map trong STL. Bạn nào chưa biết map thì Google tìm hiểu thêm nhé, ở đây mình mặc định các bạn đã biết và chỉ nói cách xử lý trên nó thôi.
map bản chất lưu các cặp <key, value>, nên tự nó đã là giải pháp cho trở ngại 1: key chính là giá trị $a_j$, còn value chính là vị trí $j$ ban đầu. Nó cài đặt bằng cây đỏ đen nên không lưu trùng key; truy cập a[x] với key chưa có thì value mặc định là $0$. Vậy khi đọc $a_j$:
a[x] == 0⇒ key $x$ chưa từng xuất hiện ⇒ gána[x] = j.a[x] != 0⇒ $x$ đã xuất hiện trước đó ở vị trí nhỏ hơn ⇒ không đụng tới.
Sau cùng map lưu các giá trị phân biệt (key) và value của mỗi key chính là vị trí xuất hiện đầu tiên – trở ngại 2 cũng xong luôn. Khi tìm kiếm, dữ liệu trong map đã được sắp xếp và cân bằng cây nên mỗi lần tìm chỉ tốn $O(\log N)$. Với mỗi $b_i$ chỉ việc in a[b_i]: có thì ra vị trí, không có thì ra $0$ đúng như đề muốn. Nói chung dùng map thì bản thân cấu trúc của nó đã làm luôn bước sắp xếp và lọc trùng cho ta, không phải mất công tự cài đặt.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
map<int, int> a;
int x;
for(int i = 1; i <= n; ++i){
cin >> x;
if(a[x] == 0){
a[x] = i;
}
}
while(m--){
cin >> x;
cout << a[x] << " ";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = {}
for i in range(1, n + 1):
x = int(data[1 + i])
if a.get(x, 0) == 0:
a[x] = i
res = []
for t in data[2 + n:2 + n + m]:
res.append(a.get(int(t), 0))
print(*res)dict (bảng băm) với a.get(x, 0) để thay cho map: không có key thì trả về $0$ mà không tạo thêm phần tử mới.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho các key phân biệt (cộng thêm tối đa $M$ key rỗng mà
a[x]tự tạo ra khi tìm số không có). - Thời gian: $N$ lần chèn và $M$ lần tìm, mỗi lần $O(\log N)$ ⇒ $O((N + M) \cdot \log N)$.
Thực ra cách dùng map này có thể chạy chậm hơn cách 2 một chút vì tốn thêm chi phí cân bằng cây, nhưng nói chung vẫn không bị TLE khi nộp bài. Nên nếu đang trong cuộc thi có tính thời gian thì là mình, mình sẽ dùng cách map này để code ra nhanh gọn xong bài ahihi 😁.
upper_bound) đều cho đúng output ví dụ của đề, và đã được so với một chương trình vét cạn độc lập trên 500 bộ test ngẫu nhiên (có số âm, nhiều số trùng, số cần tìm nhỏ hơn mọi phần tử) – khớp hết. Với $N = M = 10^5$, trên máy mình bản C++ cách 2 chạy khoảng 0,12 – 0,26 giây, cách 3 khoảng 0,16 – 0,65 giây (giá trị ngẫu nhiên tới $10^9$ thì map chậm hơn rõ), còn cách 1 với test xấu nhất (mọi số của $b$ đều không có trong $a$) mất khoảng 6,7 giây ⇒ TLE đúng như phân tích. Bản Python cách 2 chạy khoảng 1,2 – 1,5 giây, bản bisect và bản dict nhanh hơn (dưới 1 giây).- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét