Hướng dẫn giải của SETMAP03: Loại bỏ phần tử trùng lặp
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 gồm ~n~ số. Cần loại bỏ các số trùng lặp nhưng giữ nguyên thứ tự xuất hiện của các số.
Cách làm
- Dùng một tập hợp (set) để nhớ những số đã xuất hiện trước đó.
- Duyệt dãy theo thứ tự. Nếu số ~x~ chưa có trong tập hợp thì thêm ~x~ vào tập hợp và lưu ~x~ vào mảng kết quả.
- Nếu ~x~ đã có trong tập hợp nghĩa là đã xuất hiện trước đó, nên bỏ qua.
- Cuối cùng in mảng kết quả trên một dòng, các số cách nhau bởi khoảng trắng.
- Bẫy: ~n~ có thể tới ~2 \cdot 10^5~ nên không được dùng vòng lặp kiểm tra từng cặp số.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
set<int> da_gap; // các giá trị đã xuất hiện trước đó
int kq[200005]; // dãy kết quả, giữ đúng thứ tự xuất hiện
int dem = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
// Chỉ lấy phần tử lần đầu tiên xuất hiện
if (da_gap.count(x) == 0) {
da_gap.insert(x);
kq[dem] = x;
dem++;
}
}
for (int i = 0; i < dem; i++) {
if (i > 0) {
cout << " ";
}
cout << kq[i];
}
cout << "\n";
return 0;
}
Bình luận