给定一个数组(array)，将数组向右旋转k步(k>=0)。
不需要输出，只改变原来的数组就可以。
每次循环将数组的元素都向后移动一位，循环k次。
class Solution: def rotate(self, nums: List[int], k: int) -> None: for i in range(k): previous = nums[-1] for j in range(len(nums)): nums[j], previous = previous, nums[j]
nums[j], previous = previous, nums[j]中，nums[j]和previous都是原先的值；
nums[j] = previous
previous = nums[j]
中，nums[j]的值改变成previous的值了，所以两者的结果不同。
Time complexity: O(n×k)\mathcal{O}(n \times k)O(n×k). All the numbers are shifted by one step(O(n)\mathcal{O}(n)O(n)) k times(O(n)\mathcal{O}(n)O(n)).
Space complexity: O(1)\mathcal{O}(1)O(1). No extra space is used.
构建一个新的数组，并将元素直接移动到正确的位置。
用求余的方式来实现错位。
class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) a = [0] * n for i in range(n): a[(i + k) % n] = nums[i] #%求余 nums[:] = a
Time complexity: O(n)\mathcal{O}(n)O(n). One pass is used to put the numbers in the new array. And another pass to copy the new array to the original one.
Space complexity: O(n)\mathcal{O}(n)O(n). Another array of the same size is used.
循环替换
class Solution: def rotate(self, nums: List[int], k: int) -> None: 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
Time complexity: O(n)\mathcal{O}(n)O(n). Only one pass is used.
Space complexity: O(1)\mathcal{O}(1)O(1). Constant extra space is used.
使用列表reverse
class Solution: def reverse(self, nums: list, start: int, end: int) -> None: while start < end: nums[start], nums[end] = nums[end], nums[start] start, end = start + 1, end - 1 def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k %= n self.reverse(nums, 0, n - 1) self.reverse(nums, 0, k - 1) self.reverse(nums, k, n - 1)
Time complexity: O(n)\mathcal{O}(n)O(n). nnn elements are reversed a total of three times.
Space complexity: O(1)\mathcal{O}(1)O(1). No extra space is used.
原文：https://www.cnblogs.com/jialinliu/p/12815546.html