数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用块交换算法进行数组旋转的JavaScript程序
数组元素的旋转是指将给定数组的元素向左或向右移动特定数量的位置。我们将假设数组是循环的，并将边缘元素旋转到另一端。块交换算法用于数组旋转，它通过交换技术而不是旋转来旋转数组的元素。我们将实现递归和迭代两种方法。
输入
The given array is [ 1, 2, 3, 4, 5, 6, 7]. The number of rotations by which we have to rotate is 3.
输出
[4, 5, 6, 7, 1, 2, 3]
解释
我们可以使用交换算法得到结果，我们将在下一节中实现它。
递归方法
在这种方法中，我们将尝试假设我们有两个数组，第一个数组的大小为给定的旋转次数，另一个数组的大小为总数减去给定的元素个数。
如果第一个数组的大小较小，我们将把第一个数组的元素与等于第一个数组大小的最后一个元素交换，如果第一个数组的大小较大，我们将把等于第二个数组大小的第一个元素与给定数组交换。
对于剩余的元素，我们将通过更改交换数组来调用递归函数。
示例
function swap(arr, st, si, k){
// function to traverse over the array and swap the elements
for(var i = 0; i < k; i++) {
var temp = arr[st + i];
arr[st + i] = arr[si + i];
arr[si + i] = temp;
}
return arr;
}
function rotate(arr, k, n){
// if the number of rotations is zero or equal to the size of array
// in this case we don't have to rotate the array
if(k == 0 || k == n){
return;
}
// special case when the number of elements to rotate
// is half of the size of the given array
if(n == 2*k){
arr = swap(arr, 0, n - k, k);
return;
}
// if the first part is short
if(2*k < n) {
arr = swap(arr, 0, n - k, k);
rotate(arr, k, n - k);
}
else{
// if second part is short
arr = swap(arr, 0, k, n - k);
rotate(arr + n - k, 2 * k - n, k);
}
}
// function to print the given array
function print(arr){
var temp = "";
for(var i = 0; i < arr.length; i++){
temp += arr[i] + " ";
}
console.log(temp);
}
//Defining the array
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);
// rotating the array
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);
时间和空间复杂度
上述代码的时间复杂度为 N，其中 N 是给定数组的大小。
上述代码的空间复杂度为 N，但这仅在我们考虑递归栈占用的内存时才适用。
迭代方法
迭代方法与递归方法相同，唯一的区别是，我们使用 while 循环而不是递归调用。让我们看看代码。
示例
function swap(arr, st, si, k){
// function to traverse over the array and swap the elements
for(var i = 0; i < k; i++) {
var temp = arr[st + i];
arr[st + i] = arr[si + i];
arr[si + i] = temp;
}
return arr;
}
function rotate(arr, k, n){
// if the number of rotations is zero or equal to the size of array
// in this case we don't have to rotate the array
if(k == 0 || k == n){
return;
}
var i = k;
var j = n - k;
while (i != j){
if(i < j){
// if the first array is shorter
arr = swap(arr, k - i, k + j - i, i);
j -= i;
}
else{
// if the second array is shorter
arr = swap(arr, k - i, k, j);
i -= j;
}
}
arr = swap(arr, k - i, k, i);
}
// function to print the given array
function print(arr){
var temp = "";
for(var i = 0; i < arr.length; i++){
temp += arr[i] + " ";
}
console.log(temp);
}
// defining the array
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);
// rotating the array
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);
时间和空间复杂度
上述代码的时间复杂度为 N，其中 N 是给定数组的大小。
上述代码的空间复杂度为 1 或常数，因为我们在这里没有使用任何额外的空间。
结论
在本教程中，我们实现了一个 JavaScript 程序，使用块交换算法将数组旋转给定的次数。我们已经实现了块交换算法的迭代方法，其时间复杂度为 O(N)，空间复杂度为 O(1)，同时递归方法的时间复杂度为 O(N)，空间复杂度为 O(N)。
更新于：2023年4月20日
170 次浏览
广告