如何旋转数组？

Question

我有以下问题要测试:

通过k步向右旋转n个元素的数组.

例如,当n = 7且k = 3时,阵列[1,2,3,4,5,6,7]旋转到[5,6,7,1,2,3,4].您知道解决此问题的方式有多少种？

我的中间阵列解决方案:

使用Space is O(n)和time 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 -反转算法（好一个）：

算法：

旋转（arr []，d，n）

反向（arr[]，l，n）；

反向(arr[], 1, nd) ;

反向（arr[]，n - d + 1，n）；

让 AB 是输入数组的两部分，其中 A = arr[0..nd-1] 和 B = arr[nd..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)
{
  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);
}

时间复杂度：O(n)

辅助空间：O(1)

方法 3 -一一旋转：

righttRotate(arr[], d, n)

开始

对于 i = 0 到 i < d

将 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)
{
  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;
}

时间复杂度：O(n*d)

辅助空间：O(1)

Answer 2

你不需要for- 循环.

public int[] rotate(int[] nums, int k) {
     if(k > nums.length) 
          k=k%nums.length;

     int[] result = new int[nums.length];
     System.arraycopy( nums, k+1, result, 0, k );
     System.arraycopy( nums, 0, result, k+1, nums.length-1 );

     //Case 1: The rotated array will be assigned to the given array "nums"
     nums = result;

     return result; //Case 2: method returns the rotated array
}

可以在http://docs.oracle.com/javase/7/docs/api/java/lang/System.html找到arraycopy规范.

不是testet.方法的总体复杂性旋转O(1).

如果您的问题是关于所有可能的排列,请查看 Java代码以获取数字列表的排列

另一个建议是查看Java Collection API,它提供了许多复杂的数据结构和常见的排序算法,这些算法都以非常有效的方式实现.

编辑由于评论.

该方法返回一个旋转的数组.您可以在外部方法中使用此方法,如下所示:(只是伪代码)

void rotator(int[] nums) {        
       int rotated[] = nums;
       //Can be invoked iteraritve or within a loop like this
       rotated = rotate(rotated, 3);          
}