1, 题目

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

示例 1:

  1. 输入: [1,2,3,4,5,6,7] 和 k = 3
  2. 输出: [5,6,7,1,2,3,4]
  3. 解释:
  4. 向右旋转 1 步: [7,1,2,3,4,5,6]
  5. 向右旋转 2 步: [6,7,1,2,3,4,5]
  6. 向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

  1. 输入: [-1,-100,3,99] 和 k = 2
  2. 输出: [3,99,-1,-100]
  3. 解释:
  4. 向右旋转 1 步: [99,-1,-100,3]
  5. 向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. object Solution {
  2.     def rotate(nums: Array[Int], k: Int): Unit = {
  3.         val x = nums.length - k % nums.length
  4.         f(nums, 0, x)
  5.         f(nums, x, nums.length)
  6.         f(nums, 0, nums.length)
  7.     }
  9.     def f(nums: Array[Int], start: Int, end: Int): Unit = {
  10.         var i = start
  11.         var j = end - 1
  12.         while (i < j) {
  13.             val t = nums(i)
  14.             nums(i) = nums(j)
  15.             nums(j) = t
  16.             i += 1
  17.             j -= 1
  18.         }
  19.     }
  20. }
  1. class Solution:
  2.     def rotate(self, nums: List[int], k: int) -> None:
  3.         """
  4.         Do not return anything, modify nums in-place instead.
  5.         """
  6.         x = len(nums) - k % len(nums)
  7.         self.f(nums, 0, x)
  8.         self.f(nums, x, len(nums))
  9.         self.f(nums, 0, len(nums))
  11.     def f(self, nums: List[int], start: int, end: int) -> None:
  12.         while start < end:
  13.             nums[start], nums[end-1] = nums[end-1], nums[start]
  14.             start += 1
  15.             end -= 1