Mô phỏng thuật toán Xoay mảng bằng đảo ba lần

Rotate Array (Reversal) · Nhóm: Mảng

Xoay mảng tại chỗ bằng mẹo đảo ba lần, không cần mảng phụ.

Ý tưởng

Chuẩn hoá số bước: k = k mod n.

Đảo toàn bộ mảng để đưa k phần tử cuối lên đầu (nhưng đang lộn ngược).

Đảo lại k phần tử đầu, rồi đảo lại phần còn lại · mỗi đoạn đúng thứ tự trở lại.

Vì sao đúng

Chỉ dùng thao tác đảo tại chỗ với hai con trỏ tiến vào giữa, nên tổng thời gian O(n) và bộ nhớ phụ O(1), không cần sao chép mảng.

Mã Python

def rotate(a, k):
    n = len(a)
    k %= n                       # normalize shift
    def reverse(lo, hi):         # reverse a[lo..hi] in place
        while lo < hi:
            a[lo], a[hi] = a[hi], a[lo]
            lo, hi = lo + 1, hi - 1
    reverse(0, n - 1)            # reverse the whole array
    reverse(0, k - 1)           # reverse the first k
    reverse(k, n - 1)           # reverse the rest
    return a

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