Rotate an array with an arbitrary step size without creating a second array

Question

So, for a step of size 1, I want an array:

{1, 2, 3, 4} 

To become:

 {4, 1, 2, 3} 

And for a step of size 2, the result will be:

 {3, 4, 1, 2} 

This is the code I'm using now:

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

The code works fine, but is it possible to achieve this without creating a helper array (which is the array in the code above)?

Thanks!

Answer 1

You can do this without creating a large array:

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

So, for an array of 100,000 and a step size of 10, it creates a 10-element array, copies the last 10 elements into it, copies the first 999,990 elements later, and then copies it from the temporary array back to the beginning of the array.

Answer 2

Use not me ++, but I + = shiftSize and several cycles (the number of them will be equal to gcd in the file array.length and shifSize).

Then you only need one int as a buffer, and the runtime will be pretty much the same.

Answer 3

You can do this with a pair of loops, but it's not that simple. In this case, using recursion is easier.

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

prints

 [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] 

Answer 4

Yes, you may only need to temporarily save one element in addition to the array. Basically what you want to do is:

• save last item in tmp var
• move all elements to the right by one, starting from the second to the last element
• sotre tmp var as the first element
• repeat step 1 depending on your step

Answer 5

This is not verified ...

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

The idea I'm trying to implement is as follows:

• If step not a factor of length , then incrementing the index ( pos ) by step modulo length , starting from zero, visits each element of the array once after length iterations.

• If step is a coefficient of length , then the index (increment, as indicated above) will return to the starting point after length / step iterations. But if you then increment by one, you can process a loop starting at 1, then at 2, etc. After length iterations, we will visit each element of the array once.

The rest simply swings the values ​​of the elements when we cyclically move the indices of the elements ... with some tweaking when we increment to the next cycle.

Other complete solutions have the advantage of being much easier to understand, but this does not require additional heap storage (i.e. no temporary array) and does the job in the cycles of the array.length loop.

Answer 6

In n-1 iterations

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