Hướng dẫn giải của [200 đề thầy Đức] Bài 143: Phần tử nhỏ thứ k trong dãy
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho dãy $A$ gồm $N$ số nguyên và số $K$. Cần tìm phần tử nhỏ thứ $K$ trong dãy, tức là phần tử đứng ở vị trí thứ $K$ khi sắp xếp dãy tăng dần (các phần tử bằng nhau được tính riêng).
Sub 1: Vét cạn — ~O(K \cdot N)~, dùng khi ~K \le 100~
Lấy phần tử nhỏ nhất của dãy, loại nó đi, rồi lặp lại đúng $K$ lần. Lần cuối cùng lấy được chính là phần tử nhỏ thứ $K$.
Kết quả chấm riêng sub này: đúng 12/21 test (9 test quá giờ vì $K$ lớn hơn miền của sub).
Sub 2: Sắp xếp — ~O(N \log N)~
Sắp xếp dãy tăng dần rồi lấy phần tử ở vị trí $K$ (chỉ số $K-1$ trong C++). Cách này đơn giản và đủ nhanh với $N \le 5 \cdot 10^4$.
Bẫy cần chú ý: chỉ số bắt đầu từ $0$ trong C++, nên phải lấy B[K-1], không phải B[K].
Kết quả chấm riêng sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc $T$, rồi với mỗi bộ dữ liệu đọc $N$, dãy $A$ và $K$. Nếu $K \le 100$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test có $K$ nhỏ nếu sub2 chưa làm kịp.
#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<int> A;
// Sub 1: vét cạn — lấy phần tử nhỏ nhất K lần, mỗi lần lấy xong thì loại đi
// (mỗi lần quét cả dãy để tìm min). Độ phức tạp O(K * N). Dùng khi K <= 100
void sub1() {
vector<int> B = A;
int res = 0;
for (int t = 0; t < K; t++) {
int idx = 0;
for (int i = 1; i < (int)B.size(); i++)
if (B[i] < B[idx]) idx = i;
res = B[idx];
B.erase(B.begin() + idx); // loại phần tử nhỏ nhất vừa lấy
}
cout << res << "\n";
}
// Sub 2: sắp xếp dãy rồi lấy phần tử thứ K. Độ phức tạp O(N log N). Dùng cho mọi K
void sub2() {
vector<int> B = A;
sort(B.begin(), B.end());
cout << B[K - 1] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> N;
A.assign(N, 0);
for (int i = 0; i < N; i++) cin >> A[i];
cin >> K;
if (K <= 100) sub1(); // K nhỏ: vét cạn cho chắc
else sub2(); // K lớn: sắp xếp
}
return 0;
}
Bình luận