力扣每日一练（24-1-17）：轮转数组

方法一：使用额外的数组

? ? ? ? 这个方法的思路是创建一个新的数组，然后将每个元素放到正确的位置上。新数组的第i个元素应该是原数组的第(i + len(nums) - k) % len(nums)个元素。

def rotate(nums, k):
    n = len(nums)
    rotated = [0] * n
    for i in range(n):
        rotated[(i + k) % n] = nums[i]
    nums[:] = rotated

方法二：环状替换

? ? ? ? 这个方法的思路是将每个元素移动到正确的位置上，然后再将下一个元素移动，直到遍历完所有元素。

def rotate(nums, k):
    n = len(nums)
    k %= n
    start = count = 0
    while count < n:
        current, prev = start, nums[start]
        while True:
            next_idx = (current + k) % n
            nums[next_idx], prev = prev, nums[next_idx]
            current = next_idx
            count += 1
            if start == current:
                break
        start += 1

方法三：数组反转

? ? ? ??这个方法的思路是先将所有元素反转，然后反转前k个元素，最后反转剩下的元素。

def rotate(nums, k):
    def reverse(i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    n = len(nums)
    k %= n
    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)

? ? ? ? 以上三种方法的时间复杂度都是O(n)，其中n是数组的长度。方法一的空间复杂度是O(n)，方法二和方法三的空间复杂度是O(1)。