JavaScript数组右旋算法程序

数组右旋是指将数组元素向右旋转给定次数。对于位于边缘的数字，假设数组呈环状，它们将移动到右旋后的第一个索引。我们将实现一个完整的代码来实现该算法并进行解释。

示例

Let us assume we have given array as
[1, 2, 3, 4, 5, 6, 7, 8, 9]
The number of right rotations of the array is 3
Output:
7 8 9 1 2 3 4 5 6

解释

第一次旋转时，所有元素都向右移动，最后一个元素将移到第零个索引。

9 1 2 3 4 5 6 7 8

第二次旋转时，所有元素再次移到下一个索引，最后一个元素移到第零个索引。

8 9 1 2 3 4 5 6 7

最终，经过第三次旋转后，数组如下所示

7 8 9 1 2 3 4 5 6

方法

我们已经看到了示例，现在让我们来看一下实现代码的方法。但在介绍具体方法之前，让我们先观察一下。

对于示例，我们可以观察到最后的k个元素已经到了前k个位置，而前(总数-k)个元素已经移到了最后位置。这意味着如果我们分别反转最后的k个元素和剩余的元素，然后反转整个数组，我们将得到结果数组。所以，实现代码的步骤是：

  • 首先，我们将创建一个函数来反转作为参数传递给它的数组元素，并提供反转的范围。

  • 我们将简单地遍历给定数组，从提供的起始和结束位置开始，交换当前索引的值，并将第一个指针向前移动一个位置，另一个指针向后移动一个位置。

  • 我们将创建一个函数，该函数将数组和旋转次数作为参数，首先获取旋转次数对数组大小的模。

  • 之后，我们将三次调用反转函数，传递数组和范围：

    • 最后的k个元素

    • 前(总数-k)个元素

    • 整个数组。

  • 通过这种方式，数组将向右旋转给定次数，最后我们将打印它。

示例

Open Compiler
// Function to reverse array elements 
function revArray(arr, Left, Right) {
   while (Left < Right) {
      var temp = arr[Left];
      arr[Left] = arr[Right];
      arr[Right] = temp;
      Right--;
      Left++;
   }
   return arr;
}
// function to get the mod and call another function 
function right_rotate(arr, k) {
   var len = arr.length 
   if (k == 0) return arr;
   // if rotations array 
   k = k % len;
   arr = revArray(arr, 0, (len-k-1));
   arr = revArray(arr, len-k, len-1);
   arr = revArray(arr, 0, len-1);
   return arr;
}
// Function to print elements of array 
function print(arr){
   var len = arr.length
   // traversing over the array 
   var temp = "";
   for (var i = 0; i < len; i++) {
      temp += arr[i];
      temp += " ";
   }
   console.log(temp)
}
// defining array 
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var number_of_rotations = 3
console.log("The given array is: ");
print(arr);
console.log("The Array after " +number_of_rotations+ " rotations is: ")
arr = right_rotate(arr, number_of_rotations);
print(arr);

时间和空间复杂度

上述代码的时间复杂度为O(N)，其中N是数组的大小。我们遍历数组两次，导致线性时间复杂度。

上述代码的空间复杂度为O(1)，因为我们没有使用任何额外空间。

结论

在本教程中，我们实现了一个JavaScript程序，用于将给定数组的元素向右旋转给定次数。我们实现了反转算法，首先反转前(长度-给定次数)个元素，然后反转剩余元素和所有元素。上述代码的时间复杂度为线性，空间复杂度为常数。

更新于：2023年4月12日

168 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告