Hướng dẫn giải của [VT Thiếu nhi] BÀI 03: DISTINCT
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
Cho dãy n số nguyên dương (n ≤ 10^5, a_i ≤ 10^6). In ra các giá trị khác nhau trong dãy, theo thứ tự xuất hiện lần đầu.
Ví dụ: "1 2 2 3 3 3" cho kết quả "1 2 3".
Sub 1: Vét cạn — ~O(n^2)~
Với mỗi phần tử a[i], quét lại các phần tử đứng trước; nếu chưa gặp giá trị này thì in ra. Đúng nhưng chậm khi n lớn: đạt 5/20 test (15 test quá giờ).
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("DISTINCT.INP", "r", stdin);
freopen("DISTINCT.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: với mỗi phần tử, quét lại các phần tử đứng trước; nếu chưa xuất hiện thì in ra
bool first = true;
for (int i = 0; i < n; i++) {
bool seen = false;
for (int j = 0; j < i; j++)
if (a[j] == a[i]) { seen = true; break; }
if (!seen) {
if (!first) cout << ' ';
cout << a[i];
first = false;
}
}
cout << '\n';
return 0;
}
Sub 2: Dùng set ghi nhớ — ~O(n log n)~
Dùng set<int> lưu các giá trị đã gặp. Khi đọc một số, seen.insert(x).second trả về true nếu x chưa có trong tập, khi đó in x ra. Cách này giữ đúng thứ tự xuất hiện lần đầu. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("DISTINCT.INP", "r", stdin);
freopen("DISTINCT.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// Dùng set để nhớ các giá trị đã gặp; giữ thứ tự xuất hiện lần đầu
set<int> seen;
bool first = true;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (seen.insert(x).second) { // insert trả về true nếu x chưa có trong set
if (!first) cout << ' ';
cout << x;
first = false;
}
}
cout << '\n';
return 0;
}
Bình luận