Rotate Array

Q: Điều gì xảy ra khi k lớn hơn độ dài của mảng?

Cứ sau n bước, mảng lại trở về thứ tự ban đầu, nên chỉ có k mod n bước là quan trọng. Xoay [10, 20, 30] đi 7 bước cũng giống như xoay 1 bước, cho ra [30, 10, 20] . Khi k là bội số của n , mảng không thay đổi.

Q: Làm thế nào để xoay mảng sang trái?

Phép xoay trái k vị trí tương đương với phép xoay phải n - (k mod n) vị trí. Với cách đảo ngược, hãy đảo ngược k mod n giá trị đầu tiên, rồi đến phần còn lại, sau đó đảo ngược toàn bộ mảng. Cả hai cách đều có độ phức tạp thời gian O(n).

Trung bìnhMảng và chuỗi Hai con trỏ

+10

Bạn nhận được một mảng số nguyên nums và một số k. Xoay mảng sang phải k bước: mỗi bước, mọi giá trị dịch sang phải một vị trí, còn giá trị cuối cùng chuyển về đầu mảng. Trả về mảng sau khi xoay.

k có thể lớn hơn nhiều so với độ dài của mảng.

Hàm

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: mảng (array) số nguyên cần xoay
kinteger: cần xoay sang phải bao nhiêu bước
Trả vềinteger-array: các số được xoay sang phải k bước

Ràng buộc

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

Ví dụ

Đầu vào: nums = [4, 9, 1, 6, 3]k = 2
Đầu ra: [6, 3, 4, 9, 1]
Giải thích: Hai bước sang phải đưa hai giá trị cuối cùng, 6 và 3, lên đầu. Ba giá trị còn lại dịch sang phải hai vị trí và giữ nguyên thứ tự: [6, 3, 4, 9, 1].

Câu hỏi mở rộng

Bạn có thể xoay tại chỗ bằng cách chuyển từng giá trị thẳng đến (i + k) mod n và tiếp tục di chuyển giá trị bị thay thế không? Cách đó tạo ra bao nhiêu chu kỳ?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Cứ sau mỗi n bước, mảng lại trở về vị trí ban đầu, vì vậy trước tiên hãy giảm k, vốn có thể lên đến 10^9, xuống còn k mod n. Sau đó, ghi từng giá trị thẳng vào chỉ số cuối cùng của nó trong một mảng thứ hai, hoặc đạt cùng kết quả ngay trong mảng bằng ba lần đảo ngược và bộ nhớ bổ sung O(1).

Sao chép từng giá trị vào chỉ số mới của nó

Ý tưởng

Sau k bước, giá trị ở chỉ số i nằm tại (i + k) mod n, vì vậy hãy ghi trực tiếp giá trị vào đó mà không cần thực hiện từng bước. Trước tiên, rút gọn k thành k mod n: xoay n bước sẽ đưa mọi giá trị trở về vị trí ban đầu, nên với k = 7 và n = 3, chỉ còn một bước cần thực hiện.

Chỉ cần một lượt để đặt đủ n giá trị: thời gian O(n), cộng thêm bộ nhớ O(n) cho kết quả. Bạn không thể ghi trực tiếp vào nums theo cách này, vì mỗi lần ghi sẽ ghi đè lên một giá trị mà bạn chưa di chuyển.

Thuật toán

Đặt n bằng độ dài của nums và thay k bằng k mod n.
Tạo một mảng kết quả có độ dài n.
Với mỗi chỉ số i, lưu nums[i] tại result[(i + k) mod n].
Trả về kết quả.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Ba lần đảo ngược tại chỗ

Ý tưởng

Chia mảng thành A, gồm n-k giá trị đầu tiên, và B, gồm k giá trị cuối cùng. Mảng sau khi xoay là B theo sau bởi A, mỗi khối giữ nguyên thứ tự cũ. Đảo ngược toàn bộ mảng sẽ đảo cả thứ tự các khối lẫn thứ tự bên trong mỗi khối, nên B đứng trước nhưng bị đảo ngược, A cũng vậy. Đảo ngược từng khối một lần nữa sẽ khôi phục thứ tự bên trong khối.

Với [4, 9, 1, 6, 3] và k = 2: đảo ngược toàn bộ sẽ cho [3, 6, 1, 9, 4], đảo ngược hai giá trị đầu tiên sẽ cho [6, 3, 1, 9, 4], và đảo ngược ba giá trị cuối cùng sẽ cho [6, 3, 4, 9, 1].

Mỗi giá trị được hoán đổi nhiều nhất hai lần, nên thời gian chạy là O(n) và bộ nhớ bổ sung chỉ gồm vài biến chỉ số (O(n) trong R, vì R sao chép vector khi hàm hỗ trợ đảo ngược thay đổi nó).

Thuật toán

Gán n bằng độ dài của nums rồi thay k bằng k mod n.
Đảo ngược toàn bộ mảng, từ chỉ số 0 đến n-1.
Đảo ngược khối đầu tiên, từ chỉ số 0 đến k-1.
Đảo ngược khối thứ hai, từ chỉ số k đến n-1.
Trả về nums.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Lỗi thường gặp và trường hợp biên

Quên lấy k mod n. Với k = 10^9, xoay từng bước sẽ không bao giờ kết thúc, còn đảo ngược k giá trị đầu tiên sẽ đọc vượt quá cuối mảng.
Cắt lát mà không lấy modulo. Trong Python, nums[-k:] + nums[:-k] với k = 7 và n = 3 trả về mảng không đổi, vì cả hai lát cắt đều dừng ở mép mảng.
Đảo ngược sai thứ tự. Đảo ngược hai khối trước rồi mới đảo ngược toàn bộ mảng là phép xoay trái.
Lệch một vị trí ở ranh giới giữa hai khối: khối đầu tiên kết thúc tại chỉ số k-1 và khối thứ hai bắt đầu tại k. Trong Lua và R, hai ngôn ngữ đếm từ 1, các khối là 1..k và k+1..n.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Rotate Array là bao nhiêu?

O(n) cho cả cách sao chép lẫn cách đảo ngược ba lần, vì mỗi giá trị được di chuyển một số lần không đổi. Trước tiên, giảm k bằng k mod n để giá trị k rất lớn không ảnh hưởng. Thay vào đó, xoay từng bước một sẽ tốn O(n × k).

Điều gì xảy ra khi k lớn hơn độ dài của mảng?

Cứ sau n bước, mảng lại trở về thứ tự ban đầu, nên chỉ có k mod n bước là quan trọng. Xoay [10, 20, 30] đi 7 bước cũng giống như xoay 1 bước, cho ra [30, 10, 20]. Khi k là bội số của n, mảng không thay đổi.

Làm thế nào để xoay mảng sang trái?

Phép xoay trái k vị trí tương đương với phép xoay phải n - (k mod n) vị trí. Với cách đảo ngược, hãy đảo ngược k mod n giá trị đầu tiên, rồi đến phần còn lại, sau đó đảo ngược toàn bộ mảng. Cả hai cách đều có độ phức tạp thời gian O(n).

def rotate(nums, k):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [4, 9, 1, 6, 3]
k = 2

Đầu ra mong đợi

[6, 3, 4, 9, 1]