java - 如何旋转数组？

我有以下问题要测试:

我在中间数组中的解决方案:
空间是 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 )空间中使用气泡旋转(如气泡排序)来做到这一点？

最佳答案

方法 1 - 反转算法 (好一个):



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



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

A = [1, 2, 3, 4, 5] 和 B = [ 6, 7]



这是代码片段:

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}

元素首先在第一组中移动
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)
{
  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);
}

方法三 - 一一旋转:



结尾

要旋转一，将 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;
}

关于java - 如何旋转数组？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31174840/