旋转数组

题目

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

示例

输入: 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]

题解

方法一

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything,  modify nums in-place instead.
 */
var rotate = function (nums, k) {
  k = k % nums.length
  reverse(nums, 0, nums.length - 1)
  reverse(nums, 0, k - 1)
  reverse(nums, k, nums.length - 1)
}
function reverse(arr, start, end) {
  while (start < end) {
    const temp = arr[start]
    arr[start] = arr[end]
    arr[end] = temp
    start++
    end--
  }
}

方法二

var rotate = function (nums, k) {
  k = k % nums.length
  for (let i = 0; i < k; i++) {
    nums.unshift(nums.pop())
  }
}