📑 题目：189. 旋转数组

🚀 本题 LeetCode 传送门

题目大意

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

解题思路

  • 解法二，使用一个额外的数组，先将原数组下标为 i 的元素移动到 (i+k) mod n 的位置，再将剩下的元素拷贝回来即可。
  • 解法一，由于题目要求不能使用额外的空间，所以本题最佳解法不是解法二。翻转最终态是，末尾 k mod n 个元素移动至了数组头部，剩下的元素右移 k mod n 个位置至最尾部。确定了最终态以后再变换就很容易。先将数组中所有元素从头到尾翻转一次，尾部的所有元素都到了头部，然后再将 [0,(k mod n) − 1] 区间内的元素翻转一次，最后再将 [k mod n, n − 1] 区间内的元素翻转一次，即可满足题目要求。

代码

  1. package leetcode
  3. // 解法一 时间复杂度 O(n)，空间复杂度 O(1)
  4. func rotate(nums []int, k int) {
  5.  k %= len(nums)
  6.  reverse(nums)
  7.  reverse(nums[:k])
  8.  reverse(nums[k:])
  9. }
  11. func reverse(a []int) {
  12.  for i, n := 0, len(a); i < n/2; i++ {
  13.   a[i], a[n-1-i] = a[n-1-i], a[i]
  14.  }
  15. }
  17. // 解法二 时间复杂度 O(n)，空间复杂度 O(n)
  18. func rotate1(nums []int, k int) {
  19.  newNums := make([]int, len(nums))
  20.  for i, v := range nums {
  21.   newNums[(i+k)%len(nums)] = v
  22.  }
  23.  copy(nums, newNums)
  24. }