java - 如何旋转数组？

Question

我有以下问题需要测试:

Rotate an array of n elements to the right by k steps.

For instance, with n = 7 and k = 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?

我在中间数组中的解决方案:

空间是O(n)，时间是O(n)，我可以创建一个新数组，然后将元素复制到新数组。然后使用 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);
}

但是有没有更好的方法我们可以在 O(1) 空间中使用冒泡旋转(如冒泡排序)来做到这一点？

Answer 1

方法 1 - 反转算法(好的方法):

Algorithm:

rotate(arr[], d, n)

reverse(arr[], l, n);

reverse(arr[], 1, n-d) ;

reverse(arr[], n - d + 1, n);

设 AB 是输入数组的两个部分，其中 A = arr[0..n-d-1] 和 B = arr[n-d..n-1]。该算法的思想是:

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 */

对于 arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 和 n = 7

A = [1, 2, 3, 4, 5] 和 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]

这是代码片段:

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--;
   }
}

方法 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}

1. 元素在第一个集合中首先移动 arr[] 在这一步之后 --> {4 2 3 7 5 6 10 8 9 1 11 12}

2. 然后是第二盘。 arr[] 在这一步之后 --> {4 5 3 7 8 6 10 11 9 1 2 12}

3. 终于进入第三局。 arr[] 在这一步之后 --> {4 5 6 7 8 9 10 11 12 1 2 3}

代码如下:

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)

方法 3 - 一个一个地旋转:

righttRotate(arr[], d, n)

start

For i = 0 to i < d

Right rotate all elements of arr[] by one

结束

要旋转一个，将 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)
{
  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)