[189] 轮转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 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]

示例 2:

输入：nums = [-1,-100,3,99], k = 2

输出：[3,99,-1,-100]

解释:

向右轮转 1 步: [99,-1,-100,3]

向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 10^5

-2^31 <= nums[i] <= 2^31 - 1

0 <= k <= 10^5

进阶：

尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

这道题要求使用原地算法，因此我们必须注意处理数据的先后顺序。因此，我们需要首先将被原地替换的数据优先存储起来，防止被覆盖。

最直观的想法是，将轮转后从尾部替换到头部的数据都记录下来，存成一个数组tempArr。之后，将这些位置上的数据替换成正确的数据。最后，将记录下来的数据从头开始，依次覆盖nums中的对应位置。

function rotate(nums: number[], k: number): void {
  const len = nums.length;
  k = k % len;

  const tempArr = [];
  for (let i = len - k; i < len; i++) {
    tempArr.push(nums[i]);
  }

  for (let i = len - 1; i >= k; i--) {
    nums[i] = nums[i - k];
  }

  for (let i = 0; i < tempArr.length; i++) {
    nums[i] = tempArr[i];
  }
}

这样的时间复杂度为O(3k)，应该与要求的时间复杂度O(n)在同一水平上。但是这里需要O(k)的空间复杂度。如果要求使用O(1)的空间，就得另想办法了。

我们注意到，当我们将nums中的元素向右移动 k 次后，尾部的k个元素会移动至头部，其余元素向后移动 k 个位置。

而将nums翻转后，尾部的k个元素恰好就放在了前k个位置。而此时将前k个元素，与后面的元素分别再做依次翻转，即可得到最后的结果。

此时，问题就变成了普通的数组翻转问题了，使用双指针就能搞定。

此时的空间复杂度为O(1)，时间复杂度为O(2n)。

function rotate(nums: number[], k: number): void {
  const len = nums.length;
  k = k % len;

  reverse(0, len - 1);
  reverse(0, k - 1);
  reverse(k, len - 1);

  function reverse(start: number, end: number) {
    let left = start;
    let right = end;
    while (left < right) {
      const temp = nums[left];
      nums[left] = nums[right];
      nums[right] = temp;
      left++;
      right--;
    }
  }
}