如何旋转数组? [英] How to rotate an array?
问题描述
我有以下问题要测试:
<块引用>将 n 个元素的数组向右旋转 k 步.
例如，对于 n = 7 和 k = 3，数组 [1,2,3,4,5,6,7] 旋转到[5,6,7,1,2,3,4].你知道多少种不同的方法来解决这个问题?
我在中间数组中的解决方案:
空间是O(n)，时间是O(n)，我可以创建一个新数组，然后将元素复制到新数组中.然后使用 System.arraycopy() 更改原始数组.
public void rotate(int[] nums, int k) {如果(k > nums.length)k = k % nums.length;int[] result = new int[nums.length];for (int i = 0; i < k; i++) {结果[i] = nums[nums.length - k + i];}int j = 0;for (int i = k; i 但是有没有更好的方法可以在 O(1) 空间中使用冒泡旋转(如冒泡排序)来做到这一点?
方法 1 - 反转算法(好一个):
<块引用>算法:
旋转(arr[], d, n)
<块引用>反向(arr[], l, n);
反向(arr[], 1, n-d);
反转(arr[], n - d + 1, n);
让 AB 是输入数组的两部分，其中 A = arr[0..n-d-1] 和 B = arr[n-d..n-1].该算法的思想是:
<块引用><块引用>反转所有得到 (AB) r = BrAr.
反转A得到BrA./* Ar 是 A 的反向 */
反向 B 获得 BA./* Br 是 B 的反向 */
对于 arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 和 n = 7
A = [1, 2, 3, 4, 5] 和 B = [ 6, 7]
<块引用><块引用>反过来，我们得到 BrAr = [7, 6, 5, 4, 3, 2, 1]
反向A，我们得到ArB = [7, 6, 1, 2, 3, 4, 5]反向B，我们得到ArBr = [6, 7, 5, 4, 3, 1, 2]
这是代码片段:
void righttRotate(int arr[], int d, int n){reverseArray(arr, 0, n-1);reverseArray(arr, 0, n-d-1);reverseArray(arr, n-d, n-1);}void reverseArray(int arr[], int start, int end){国际我;内部温度；while(开始<结束){温度 = arr[开始];arr[开始] = arr[结束];arr[end] = 温度；开始++；结尾 - ;}}方法 2 - 杂耍算法
将数组划分为不同的集合，其中集合的数量等于 n 和 d 的 GCD，并在集合内移动元素.
如果 GCD 为 1，那么元素将只在一个集合内移动，我们只需从 temp = arr[0] 开始，并不断将 arr[I+d] 移动到 arr[I]，最后将 temp 存储在正确的位置.
这是一个 n =12 和 d = 3 的例子.GCD 是 3 并且
令 arr[] 为 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
元素首先在第一组中移动arr[] 在这一步之后 --> {4 2 3 7 5 6 10 8 9 1 11 12}
然后是第二组.arr[] 在这一步之后 --> {4 5 3 7 8 6 10 11 9 1 2 12}
终于进入第三盘了.arr[] 在这一步之后 --> {4 5 6 7 8 9 10 11 12 1 2 3}
代码如下:
void leftRotate(int arr[], int d, int n){内部 i, j, k, 温度;int gcd = gcd(d, n);for (i = 0; i < gcd; i++){/* 移动块的第 i 个值 */温度 = arr[i];j = i;同时(1){k = j + d;如果 (k >= n)k = k - n;如果 (k == i)休息;arr[j] = arr[k];j = k;}arr[j] = 温度；}}int gcd(int a,int b){如果(b==0)返回一个；别的返回 gcd(b, a%b);}<块引用>
时间复杂度:O(n)
辅助空间:O(1)
方法 3 - 一一旋转:
<块引用>righttRotate(arr[], d, n)
开始
<块引用>对于 i = 0 到 i <
将 arr[] 的所有元素右旋转一个
结束
要旋转一，将 arr[n-1] 存储在临时变量 temp 中，将 arr[1] 移动到 arr[2]，将 arr[2] 移动到 arr[3] ...最后将 temp 移动到 arr[0]
以同样的例子 arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2，将 arr[] 旋转 1 次 2 次.我们第一次旋转后得到 [7, 1, 2, 3, 4, 5, 6] ，第二次旋转后得到 [ 6, 7, 1, 2, 3, 4, 5] .
她是代码片段:
void leftRotate(int arr[], int d, int n){国际我;for (i = 0; i < d; i++)leftRotatebyOne(arr, n);}void leftRotatebyOne(int arr[], int n){内部我，温度；温度 = arr[n-n];for (i = 0; i <块引用>
时间复杂度:O(n*d)
辅助空间:O(1)
I have the following problem to test:
Rotate an array of
nelements to the right byksteps.For instance, with
n = 7andk = 3, the array[1,2,3,4,5,6,7]is rotated to[5,6,7,1,2,3,4]. How many different ways do you know to solve this problem?
My solution in intermediate array:
With Space is O(n) and time is O(n), I can create a new array and then copy elements to the new array. Then change the original array by using System.arraycopy().
public void rotate(int[] nums, int k) {
if (k > nums.length)
k = k % nums.length;
int[] result = new int[nums.length];
for (int i = 0; i < k; i++) {
result[i] = nums[nums.length - k + i];
}
int j = 0;
for (int i = k; i < nums.length; i++) {
result[i] = nums[j];
j++;
}
System.arraycopy(result, 0, nums, 0, nums.length);
}
But is there a better way we can do it with bubble rotate (like bubble sort) in O(1) space?
Method 1 - The Reversal Algorithm(Good One):
Algorithm:
rotate(arr[], d, n)
reverse(arr[], l, n);
reverse(arr[], 1, n-d) ;
reverse(arr[], n - d + 1, n);
Let AB are the two parts of the input array where A = arr[0..n-d-1] and B = arr[n-d..n-1]. The idea of the algorithm is:
Reverse all to get (AB) r = BrAr.
Reverse A to get BrA. /* Ar is reverse of A */
Reverse B to get BA. /* Br is reverse of B */
For arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7
A = [1, 2, 3, 4, 5] and B = [ 6, 7]
Reverse all, we get BrAr = [7, 6, 5, 4, 3, 2, 1]
Reverse A, we get ArB = [7, 6, 1, 2, 3, 4, 5] Reverse B, we get ArBr = [6, 7, 5, 4, 3, 1, 2]
Here is the Code Snippet:
void righttRotate(int arr[], int d, int n)
{
reverseArray(arr, 0, n-1);
reverseArray(arr, 0, n-d-1);
reverseArray(arr, n-d, n-1);
}
void reverseArray(int arr[], int start, int end)
{
int i;
int temp;
while(start < end)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
Method 2 - A Juggling Algorithm
Divide the array in different sets where number of sets is equal to GCD of n and d and move the elements within sets.
If GCD is 1, then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.
Here is an example for n =12 and d = 3. GCD is 3 and
Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Elements are first moved in first set arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}
Then in second set. arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}
Finally in third set. arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}
Here is the code:
void leftRotate(int arr[], int d, int n)
{
int i, j, k, temp;
int gcd = gcd(d, n);
for (i = 0; i < gcd; i++)
{
/* move i-th values of blocks */
temp = arr[i];
j = i;
while(1)
{
k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
Time complexity: O(n)
Auxiliary Space: O(1)
Method 3 - Rotate one by one:
righttRotate(arr[], d, n)
start
For i = 0 to i < d
Right rotate all elements of arr[] by one
end
To rotate by one, store arr[n-1] in a temporary variable temp, move arr[1] to arr[2], arr[2] to arr[3] …and finally temp to arr[0]
Let us take the same example arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, rotate arr[] by one 2 times. We get [7, 1, 2, 3, 4, 5, 6] after first rotation and [ 6, 7, 1, 2, 3, 4, 5] after second rotation.
Her is Code Snippet:
void leftRotate(int arr[], int d, int n)
{
int i;
for (i = 0; i < d; i++)
leftRotatebyOne(arr, n);
}
void leftRotatebyOne(int arr[], int n)
{
int i, temp;
temp = arr[n-n];
for (i = 0; i < n-1; i++)
arr[i] = arr[i+1];
arr[n - 1] = temp;
}
Time complexity: O(n*d)
Auxiliary Space: O(1)
这篇关于如何旋转数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
