Mô phỏng thuật toán Nén toạ độ

Coordinate Compression · Nhóm: Mảng

Thay mỗi giá trị bằng hạng của nó (0..k-1) khi chỉ thứ tự tương đối là quan trọng, không phải giá trị thật.

Ý tưởng

Lấy tập giá trị khác nhau và sắp tăng dần (sorted unique).

Gán cho mỗi giá trị một hạng theo vị trí trong danh sách đã sắp: nhỏ nhất là 0.

Duyệt mảng gốc, thay từng phần tử bằng hạng tương ứng.

Vì sao đúng

Giá trị có thể rất lớn hoặc thưa, nhưng nhiều cấu trúc (cây phân đoạn, mảng đếm) chỉ cần chỉ số nhỏ gọn · nén về 0..k-1 mà vẫn giữ nguyên mọi phép so sánh.

Mã Python

def compress(a):
    vals = sorted(set(a))        # sorted unique values
    rank = {v: i for i, v in enumerate(vals)}  # value -> rank
    return [rank[x] for x in a]  # replace each value by its rank

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.