Hướng dẫn giải của [200 đề thầy Đức] Bài 153: Sắp xếp mảng 0-1-2
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Dãy chỉ gồm các số 0, 1, 2. Sau khi sắp xếp tăng dần, tất cả số 0 đứng trước, rồi đến số 1, cuối cùng là số 2. Chỉ cần đếm số lần xuất hiện của từng giá trị rồi in ra theo thứ tự.
Sub 1: Sắp xếp bằng std::sort — ~O(N \log N)~
Đọc dãy rồi dùng sort để sắp xếp trực tiếp. Đạt 18/21 test, 3 test lớn quá giờ vì N lên tới 10^6 và T lên tới 100 nên ~O(N \log N)~ chậm.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
// Sắp xếp trực tiếp bằng std::sort
sort(a.begin(), a.end());
for (int x : a) cout << x << " ";
cout << "\n";
}
return 0;
}
Sub 2: Đếm số lần xuất hiện (counting sort) — ~O(N)~
Chỉ có 3 giá trị nên đếm số 0, số 1, số 2 trong mảng ~cnt[3]~ rồi in lại theo thứ tự. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
// Đếm số lần xuất hiện của 0, 1, 2 (counting sort)
int cnt[3] = {0, 0, 0};
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
// In cnt[0] số 0, cnt[1] số 1, cnt[2] số 2
for (int v = 0; v < 3; v++)
for (int k = 0; k < cnt[v]; k++) cout << v << " ";
cout << "\n";
}
return 0;
}
Bình luận