Xoá phần tử trùng trong list Python mà vẫn giữ thứ tự
Dùng set để kiểm tra nhanh "đã gặp chưa?" và một list để giữ thứ tự xuất hiện đầu tiên.
- Kiểm tra thành viên bằng set
- Tạo list kết quả
- Vì sao chỉ dùng set(values) sẽ mất thứ tự
Set đã gặp cộng list có thứ tự
Vấn đề
Dữ liệu trùng lặp làm hỏng báo cáo, email và số liệu đếm. Bạn thường cần mỗi giá trị chỉ một lần mà vẫn giữ thứ tự xuất hiện đầu tiên của chúng, và muốn cách làm vẫn nhanh với list dài.
Hình dung đời thường
Bỏ trùng lặp giống người gác cửa cầm danh sách khách. Mỗi người đến, người gác cửa xem danh sách. Gương mặt mới thì ghi tên rồi cho vào; người quay lại lần nữa thì bị từ chối. Căn phòng đầy dần theo đúng thứ tự khách đến.
seen = set()📋 Danh sách kháchif value not in seen:🔎 Gương mặt mới?seen.add(value)✍️ Ghi tên lạiresult.append(value)🚪 Cho vào, theo đúng thứ tự đếnBỏ trùng lặp theo thứ tự là giữ lần xuất hiện đầu tiên của mỗi giá trị, dùng set để kiểm tra nhanh và list để giữ thứ tự.
Những điểm quan trọng
seenlà một set, nênvalue not in seenkiểm tra rất nhanh kể cả với list dài.seen.add(value)ghi nhận giá trị ở lần đầu nó xuất hiện.result.append(value)giữ các giá trị theo thứ tự xuất hiện đầu tiên.- Kết quả là
[3, 1, 2, 4]: số 3 thứ hai và số 1 thứ hai bị bỏ qua.
Khi nào nên sử dụng?
- Làm sạch danh sách mã, email hay tag mà vẫn giữ thứ tự.
- Bỏ các sự kiện bị lặp trong log.
- Học khi nào nên kết hợp set với list.
Khi nào chưa cần
- Thứ tự không quan trọng:
set(values)là đủ. - Giá trị không bỏ vào set được, như list hay dictionary: đổi chúng sang tuple trước hoặc so sánh theo cách khác.
Code ví dụ
def unique_in_order(values):
seen = set()
result = []
for value in values:
if value not in seen:
seen.add(value)
result.append(value)
return result
print(unique_in_order([3, 1, 3, 2, 1, 4]))
Kết quả khi chạy
[3, 1, 2, 4]
Giải thích code
Mỗi giá trị được kiểm tra đúng một lần. Nếu giá trị chưa có trong seen, nó được thêm vào cả set seen và list result. Những lần gặp lại sau đó sẽ bị bỏ qua, nên kết quả là [3, 1, 2, 4]. Vì kiểm tra thành viên trong set chỉ mất O(1), cả thuật toán chạy trong thời gian O(n).
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Kiểm tra trong chính list kết quả
value in result phải duyệt cả list mỗi lần, nên rất chậm với dữ liệu dài.
if value not in result:
result.append(value)
if value not in seen:
seen.add(value)
result.append(value)
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Loại Bỏ Phần Tử Trùng Lặp Chỉ giữ lại lần xuất hiện đầu tiên của mỗi giá trị. Dễ
- Di chuyển các số 0 Di chuyển tất cả số 0 về cuối danh sách, giữ nguyên thứ tự các phần tử còn lại. Dễ