Lọc phần tử duy nhất bảo toàn thứ tự
Trong hệ thống theo dõi hành vi học tập của AI Empire Academy, các sự kiện thao tác của người dùng được ghi nhận liên tục theo thứ tự thời gian. Do học viên có thể nhấn nút nhiều l…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: list iteration, set lookup, big o.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu rõ sự khác biệt giữa độ phức tạp tra cứu của List O(N) và Set O(1).
- Tối ưu hóa thuật toán lọc trùng lặp từ O(N2) xuống O(N).
- Bảo toàn tuyệt đối thứ tự xuất hiện đầu tiên của các phần tử.
Mô tả bài toán
Trong hệ thống theo dõi hành vi học tập của AI Empire Academy, các sự kiện thao tác của người dùng được ghi nhận liên tục theo thứ tự thời gian. Do học viên có thể nhấn nút nhiều lần, danh sách ID sự kiện thường bị lặp lại.
Bạn hãy viết hàm deduplicate_preserve_order(items: list[int | str]) -> list[int | str] nhận vào một danh sách các phần tử (có thể là số nguyên hoặc chuỗi), và trả về một danh sách mới thỏa mãn:
- Mỗi phần tử chỉ xuất hiện đúng 1 lần.
- Bảo toàn tuyệt đối thứ tự xuất hiện đầu tiên của phần tử trong danh sách ban đầu.
- Không làm biến đổi danh sách gốc được truyền vào (
pure function). - Thuật toán phải đạt độ phức tạp thời gian O(N) để chạy kịp với danh sách lên tới 105 phần tử trong thời gian 1.0 giây.
Input
Một danh sách items chứa các số nguyên hoặc chuỗi ký tự.
Output
Danh sách mới đã loại bỏ trùng lặp và giữ nguyên thứ tự ban đầu.
Ràng buộc
- Số lượng phần tử N: 0 ≤ N ≤ 105.
- Mỗi phần tử có thể là
int(từ -109 đến 109) hoặcstr(độ dài tối đa 50 ký tự). - Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
Ví dụ 1
Input
`items = [4, 5, 4, 1, 2, 5, 3]`Output
`[4, 5, 1, 2, 3]`Giải thích
- Số 4 xuất hiện đầu tiên ở vị trí 0 → giữ lại.
- Số 5 xuất hiện đầu tiên ở vị trí 1 → giữ lại.
- Số 4 tiếp theo bị trùng → bỏ qua.
- Các số 1, 2, 3 lần đầu xuất hiện → giữ lại theo thứ tự.
Ví dụ 2
Input
`items = ["ai", "python", "ai", "model", "python"]`Output
`["ai", "python", "model"]`Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.