Thuật toán Python

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.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • 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ự
Đầu vào, rồi kết quả
3
1
3
2
1
4
3
1
2
4
Các giá trị lặp được tô sáng bị bỏ qua; thứ tự được giữ nguyên.

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.

Từ người gác cửa đến code
seen = set()📋 Danh sách khách
if value not in seen:🔎 Gương mặt mới?
seen.add(value)✍️ Ghi tên lại
result.append(value)🚪 Cho vào, theo đúng thứ tự đến
Mỗi giá trị được kiểm tra một lần; chỉ giữ lần xuất hiện đầu tiên.
Định nghĩa ngắn gọn

Bỏ 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

  1. seen là một set, nên value not in seen kiểm tra rất nhanh kể cả với list dài.
  2. seen.add(value) ghi nhận giá trị ở lần đầu nó xuất hiện.
  3. result.append(value) giữ các giá trị theo thứ tự xuất hiện đầu tiên.
  4. 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ụ

Chạy code →
main.py
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]))
Lấy nút Run cho ví dụ này

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.

  1. 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.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đ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.
Chạy trong trình biên dịch Python →

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.

Sai
if value not in result:
    result.append(value)
Cách sửa
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.

Tất cả thử thách