轮转数组

题目

给定一个数组, 将数组中的元素向右移动 k 个位置, 其中 k 是非负数. 你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗?

提示:

• 1 <= n <= 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1
• 0 <= k <= 10⁵

示例

输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3

输出: [5, 6, 7, 1, 2, 3, 4]

解释:

• 向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6]
• 向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5]
• 向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4]

题解

• 先将整个数组反转
• 然后将前 k 个元素反转
• 最后将剩余的 n - k 个元素反转

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  const n = nums.length
  k = k % n

  var reverse = function (start, end, nums) {
    while (start < end) {
      ;[nums[start], nums[end]] = [nums[end], nums[start]]
      start++
      end--
    }
  }

  reverse(0, n - 1, nums)
  reverse(0, k - 1, nums)
  reverse(k, n - 1, nums)
}