旋转数组，步长任意，无需创建第二个数组。

Question

所以，如果步长为1，则我希望得到以下数组：

{1, 2, 3, 4}

变成：

{4, 1, 2, 3}

当步长为2时，结果如下：

{3, 4, 1, 2}

这是我现在使用的代码：

private static int[] shiftArray(int[] array, int stepSize) {
  if (stepSize == 0)
     return array;

  int shiftStep = (stepSize > array.length ? stepSize % array.length : stepSize);

  int[] array2 = new int[array.length];
  boolean safe = false;
  for (int i = 0; i < array.length; i++) {
     if (safe) {
        array2[i] = array[i - shiftStep];
     }
     else {
        array2[i] = array[array.length - shiftStep + i];
        safe = (i+1) - shiftStep >= 0;
     }
  }
  return array2;
}

代码运行良好，但是是否有可能在不创建帮助数组的情况下实现这一点（即上面代码中的array2）？

谢谢！

- mota

---

你可以使用这种方法：http://stackoverflow.com/questions/4454072/how-to-perform-a-circular-shift-lefton-an-array-of-int - assylias

看一下这个关于原地重排数组元素的链接：https://dev59.com/Y3I-5IYBdhLWcg3wxbjv。优化算法以特定方式重新排列，例如循环移位。 - Kazekage Gaara

http://stackoverflow.com/a/4464054/181772 比这里发布的任何内容都要快。它只执行N次移动，无论移动距离如何，并且仅需要恒定大小的临时存储。 - andrew cooke

@andrewcooke，我也认为这是完成工作的最快方法，但我的分析显示它实际上比我的方法慢得多！！Jon的方法真的非常非常快！稍后我会分享完整的结果。 - mota

@andrew cooke：System.arraycopy()非常快。而你提供的解决方案使用了模运算符（%）-这是极其慢的。 - Durandal

Answer 1

你可以不创建如此庞大的数组来完成此操作：

// void return type as it shifts in-place
private static void shiftArray(int[] array, int stepSize) {
    // TODO: Cope with negative step sizes etc
    int[] tmp = new int[stepSize];
    System.arraycopy(array, array.length - stepSize, tmp, 0, stepSize);
    System.arraycopy(array, 0, array, stepSize, array.Length - stepSize);
    System.arraycopy(tmp, 0, array, 0, stepSize);
}

对于一个长度为100,000的数组和步长为10，它创建了一个长度为10的数组，将最后10个元素复制到该数组中，将前999,990个元素复制到稍后使用，然后从临时数组中将内容复制回数组的开头。

- Jon Skeet

---

三重反转技巧（在@assylias链接的问题中提到）可以在不使用任何新数组的情况下实现它。 - yshavit

记录一下，他正在创建一个辅助数组，这是应该避免的，因为这不是 OP 的问题。;) 不管怎样，解决方案很好。 - stryba

@stryba：因此第一句话是 - 创建一个与初始数组一样大的数组和创建一个与步长一样大的数组之间有很大的区别。我采取实用的方法... - Jon Skeet

@yshavit：当然，你可以不用任何新数组来完成它。我相信有多种方法可以应对。但是，我强烈怀疑它们会更加复杂和慢。 - Jon Skeet

@JonSkeet 这个问题并不是很复杂，虽然它可能会慢一点，但速度差别不大。原地反转一个数组非常快。 - yshavit

Answer 2

你可以使用循环完成它，但这并不容易。在这种情况下，使用递归更为简单。

public static void main(String... args) {
    for (int i = 0; i < 12; i++) {
        int[] ints = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        rotateLeft(ints, i);
        System.out.println(Arrays.toString(ints));
    }
}

public static void rotateLeft(int[] array, int num) {
    rotateLeft(array, num, 0);
}

private static void rotateLeft(int[] array, int num, int index) {
    if (index >= array.length) return;
    int tmp = array[(index + num) % array.length];
    rotateLeft(array, num, index + 1);
    array[index] = tmp;
}

打印

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1]
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3]
[5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4]
[6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5]
[7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6]
[8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7]
[9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8]
[10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

- Peter Lawrey

---

好的，您没有创建一个数组，但是您使用了比数组更多的空间。 - harold

@harold确实。我相信使用一个临时数组很可能是最快的解决方案，即最初发布的内容。Jon的解决方案可能会再次稍微快一些。 - Peter Lawrey

Answer 3

不要使用 i++，而是 i += shiftSize 和一些循环（循环的次数等于数组长度和 shiftSize 的 最大公约数）。

这样你只需要一个 int 作为缓冲区，执行时间几乎相同。

- kirilloid

Answer 4

这未经过测试...

public void rotateByStep(int[] array, int step) {
    step = step % array.length;
    if (step == 0) {
        return;
    }
    int pos = step;
    int tmp = array[0];
    boolean inc = array.length % step == 0;
    for (int i = 0; i < array.length; i++) {
        int tmp2 = array[pos];
        array[pos] = tmp;
        tmp = tmp2;
        pos = (pos + step) % array.length;
        if (inc && pos < step) {
            array[pos] = tmp;
            pos++;
            tmp = array[pos];
        }
    }
}

我要实现的思路如下：

• 如果step不是length的因子，则从零开始按step模length递增一个索引（pos），在length次迭代后将访问每个数组元素一次。

• 如果step是length的因子，则按上述方式递增的索引（incremented as above）将在length / step次迭代后回到其起始点。但是，如果您然后递增一个，您可以从1开始处理周期，然后从2开始处理，以此类推。经过length次迭代后，我们将访问每个数组元素一次。

剩下的就是在通过元素索引循环时涟漪化元素值...当我们递增到下一个周期时进行一些调整。

其他完整的解决方案具有易于理解的优点，但这种方法不需要额外的堆存储（即没有临时数组），并且在array.length循环迭代中完成任务。

- Stephen C

Answer 5

是的，这是可能的，你只需要暂时存储一个数组元素之外的额外元素。 基本上你要做的是：

1. 将最后一个元素存储在tmp变量中
2. 从倒数第二个元素开始向右移动所有元素一位
3. 将tmp变量作为第一个元素存储
4. 根据你的步长重复从步骤1开始

- stryba

Answer 6

在 n-1 次迭代中

#include <stdio.h>

    int main(int argc, char **argv) {
        int k = 0, x = 0;
        int a[] = {-5,-4,-1,0,1,2,30,43,52,68,700,800,9999};
        int N = 0, R = 57; /*R = No of rotations*/
        int temp = 0, temp2  = 0, start = 0, iter = 0;

        x = 0;
        temp2 = a[x];

        N = sizeof(a) / sizeof(a[0]);
        for ( k = 0; k < N - 1; k++) {
            x = x + R;
            while ( x >= N ) {
                x = x - N;
            }
            temp = a[x];
            a[x] = temp2;
            temp2 = temp;
            if ( x == start ) {
                start = start + 1;
                x = x + 1;
                temp2 = a[x];
            }
            iter++;
        }
        a[start] = temp2;
        for ( k = 0; k < N; k++) {
            printf(" %d", a[k]);
        }
        printf("\n");
        printf("Done in %d iteration\n", iter);
        return 0;
    }

- Alam