并非“简单”的算法：数组旋转的三种方法

今天的算法是旋转数组问题：

给定一个数组，将数组向右旋转 k 步，其中 k 为非负数。

尽量想出尽可能多的解决方案，这个问题至少有 3 种不同的解决方法。你能用 O(1) 的额外空间原地求解吗？

例如，如果给定数组[1, 2, 3, 4, 5]，并要求将其2向右旋转步数，则输出应为[4, 5, 1, 2, 3]。旋转 1 步后，数组将变为[5, 1, 2, 3, 4]，因此旋转 2 步后，它将变为[4, 5, 1, 2, 3]。

在 LeetCode 上，这道题被标记为“简单”——我不确定他们是如何判断难度的。不过，我认为这道题绝非“简单”。它有很多种解法，这也是我喜欢它的原因之一，而且我认为每一种解法都有其独特的复杂性。

在这篇博文中，我将介绍三种不同的方法来解决这个问题：（1）弹出数组中的元素并取消移位，（2）创建一个新数组，其中元素一开始就移位，以及（3）反转数组的不同部分。

方法一：弹出和取消换挡

在使用数组时，有一些方法经常用到。其中之一是 `.pop( .pop())`，它会“移除数组中的最后一个元素并返回该元素”（您可以点击此处阅读更多关于 `.pop()`的信息）。例如：

const arr = [1, 2, 3]
arr.pop() // would return 3
console.log(arr) // would return [1, 2]

数组的另一个常用方法是 `.unshift()` .unshift()。该方法“将一个或多个元素添加到数组的开头，并返回数组的新长度”（您可以点击此处阅读更多关于 `.unshift()` 的信息）。例如：

const arr = [2, 3]
arr.unshift(1) // would return 3, the new length of the array
console.log(arr) // would return [1, 2, 3]

将数组向右旋转也可以理解为将数组末尾的元素移动到数组开头。在这个问题中，我们需要将数组末尾的元素移动到开头，重复此操作k次。在一个循环中（循环次数为k次），我们可以从数组末尾弹出最后一个元素，并将其移回数组开头。

例如，假设我们给定数组nums = [1, 2, 3, 4, 5]A 和k = 2B，我们需要将数组旋转 2 圈。使用 pop 和 unshift 函数，我们首先弹出最后一个元素 a，5使数组变为numsb [1, 2, 3, 4]。然后，我们取消移动 a 5，将其放在数组的开头，使数组nums变为 b [5, 1, 2, 3, 4]。

我们将再次重复这个循环，弹出4，生成nums = [5, 1, 2, 3]，然后取消 4 的移位，得到最终答案[4, 5, 1, 2, 3]。

第一种方法的编码

在开始编写解决方案之前，关于这个问题还有一点需要注意：假设给定的数组为 `a` [1, 2]，题目要求我们将其向右旋转 7 次。由于数组长度小于 7 个元素，旋转 7 次会造成很多不必要的计算。因此，在进行任何操作之前，无论是在本解决方案还是其他方法中，我们都应该k使用取模运算（%）对数组进行取模。

取模运算符返回一个数除以另一个数后的余数。例如，10/3 的余数为 1，因此10%3取模运算符返回 1。类似地，在本题中，我们希望将 10/3 的值设为1。同样地，如果 10/3 等于 1 ，且10/3等于 1 ，那么10/3 等于1，即 1/3等于 1。因此，本解答的第一行将是这一行。1kk % nums.lengthk = 7nums = [1, 2]k = k % nums.lengthk = 7%2k=1

function rotate1(nums, k) {
  k = k % nums.length;
  //...
}

我们希望执行.pop()`and`操作，.unshift()次数等于 ` ki`，所以我们将创建一个循环，循环k次数为 `i`。在 `for` 循环内部，我们将 `and` 的结果存储nums.pop()到一个名为 `i` 的变量中back。然后，我们将 `i` 的值移back回数组的开头nums。

当 for 循环停止执行后，我们将返回nums。

function rotate1(nums, k) {
  k = k % nums.length;
  for (let i = 0; i < k; i++) {
    const back = nums.pop();
    nums.unshift(back);
  }
  return nums;
}

第一种方法是在线性时间 (O(n)) 和常数空间 (O(1)) 内完成的。

方法二：创建新数组

第二种方法是创建一个新数组，其中的元素向右移动了几个k空格。这种方法的思路是，我们可以遍历nums数组，并将每个元素k向右移动几个空格。

如果元素要移动到的索引位置比数组长度还要长，会发生什么情况nums？在这种情况下，你需要使用取模运算符，计算移动到新位置后，元素与数组长度之差nums。我认为这是这种方法中比较棘手的部分，所以我会举个例子。

假设你有一个数组nums，其中[1, 2, 3]包含一个空数组arr，并且已知数组k=2向右移动两位，那么数组将向右移动两位。我们可以先移动nums数组的第一个元素1。第一个元素1位于索引 0（i = 0），我们需要将其向右移动两位。换句话说，我们希望它在数组中的位置由索引 2arr决定。i + k

现在，我们位于nums数组的索引 1 处2。我们想把它k向右移动几步，但是索引i + k是 3，这比数组的长度还要长nums。所以，为了找到新的位置2，我们应该使用索引 3 (i + k) % nums.length，也3 % 3就是索引03。因此，我们应该将元素移动2到索引03 的位置arr。

最后，我们位于nums数组的索引 2 处，即3。我们想把它k向右移动几步，而i + k是 4，比nums数组的长度要长。所以，为了找到 的新位置3，我们应该执行(i + k) % nums.length，或者4 % 3，也就是1。因此，我们应该将元素 移动到中的3索引，从而得到本题的最终结果。1arr

第二种方法的编码

首先，我们将对k第一种方法进行与之前相同的修改。然后，我们将初始化一个名为 的新空数组arr。

function rotate2(nums, k) {
  k = k % nums.length;
  let arr = [];
  //...
}

现在，我们将使用 for 循环遍历数组中的每个元素nums。对于每个索引，我们将该元素放置在数组中的新位置arr。我们可以通过执行以下操作找到新位置(i + k) % nums.length。因此，我们将数组设置arr[(i + k) % nums.length]为等于nums[i]。

function rotate2(nums, k) {
  k = k % nums.length;
  let arr = [];
  for (let i = 0; i < nums.length; i++) {
    arr[(i + k) % nums.length] = nums[i];
  }
  //...
}

现在，arr我们将得到旋转后的数组。然而，在这个问题中，我们需要修改数组nums，因此必须将数组中的每个索引值设置nums为数组中对应索引处的值arr。为此，我们可以设置另一个 for 循环。在每个索引处，我们将数组的nums[i]值设置为数组中对应索引处的值arr[i]。当 for 循环结束时，我们可以返回数组nums。

function rotate2(nums, k) {
  k = k % nums.length;
  let arr = [];
  for (let i = 0; i < nums.length; i++) {
    arr[(i + k) % nums.length] = nums[i];
  }
  for (let i = 0; i < nums.length; i++) {
    nums[i] = arr[i];
  }
  return nums;
}

第二种方法是在线性时间 (O(n)) 和线性空间 (O(n)) 内完成的。

方法三：颠倒章节顺序

在第三种方法中，我们将对nums数组的部分元素进行三次反转。第一次，我们将反转整个数组。第二次，我们将反转k数组的前几个元素。第三次，我们将反转数组的最后几个元素，从第一个元素k到最后一个元素。

这种方法的思路最好通过一个例子来说明。我们从一个数组开始[1, 2, 3, 4, 5]，现在要将它旋转两步。我们先从旋转整个数组开始。

现在，我们要旋转前几个k元素。因为kn 是 2，所以我们要旋转 0 和 1 处的元素。

最后，我们将最后一个元素从索引位置k开始向末尾旋转。这样就得到了我们想要的最终数组。

第三种方法的编码

为了实现这个解决方案，我们将编写一个嵌套函数reverse，rotate并调用它三次。不过，首先，我们将对k前两种方法进行相同的修改。

function rotate3(nums, k) {
  k = k % nums.length;
  //...
}

接下来，我们将调用该函数reverse（稍后会编写），并调用三次。reverse()该函数会接收数组、反转起始索引和反转结束索引作为参数。因此，第一次调用该函数reverse()会传入起始索引为 0 nums、0反转起始索引为 1、nums.length-1反转结束索引为 2 的参数。第二次调用该函数reverse()会传入起始索引为 0、反转nums结束索引为 2 的参数。第三次调用该函数会传入起始索引为 0、反转结束索引为 2 的参数。0k-1reverse()numsknums.length-1

function rotate3(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
  //...
}

现在，我们可以编写函数reverse，其参数为nums、start和end。在这个函数中，我们将交换起始索引和结束索引处的值，并将起始索引和结束索引向中心移动。只要起始索引小于结束索引，我们就一直执行此操作。

所以，我们将编写一个 while 循环，只要 start 小于 end，循环就会一直进行下去。在循环内部，我们将维护一个临时变量，用于存储 nums 数组在 start 索引处的值。然后，我们将 start 索引处的值设置为 end 索引处的值，并将 end 索引处的值设置为临时变量的值。我们将 start 递增，使 start 向中间移动；我们将 end 递减，使 end 向中间移动。最后，当 while 循环执行完毕后，我们将返回nums到rotate函数。

function rotate3(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(nums, start, end) {
    while (start < end) {
      let temporary = nums[start];
      nums[start] = nums[end];
      nums[end] = temporary;
      start++;
      end--;
    }
    return nums;
  }
}

每个reverse()函数执行完毕后，最后要做的是返回nums。

function rotate3(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
  return nums;

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

该解决方案可在线性时间 (O(n)) 和常数空间 (O(1)) 内完成。

如果您有任何问题或有其他解决办法，请在评论区留言！