CODEWITHSUNDEEP
javaarrayselementshift
user3332742
user3332742

Reputation: 33

Shift elements of array three places to left within java

In my java program I have an array of length 5, I want to shift the contents of the array 3 places to the left. For example [1,2,3,4,5] would become [4,5,1,2,3]. What would be the best way possible to do this? Thanks

Upvotes: 0

Views: 1821

Answers (4)

ajb
ajb

Reputation: 31699

If you need to modify the array in place and you're only allowed to use one extra temporary to hold one element, you could do it like this:

final int first = 0;
int currIndex = first;
int temp = a[currIndex];
do {
    int nextIndex = (currIndex + 3) % a.length;
    a[currIndex] = (nextIndex == first) ? temp : a[nextIndex];
    currIndex = nextIndex;
} while (currIndex != first);

which basically means temp = a[0]; a[0] = a[3]; a[3] = a[1]; a[1] = a[4]; a[4] = a[2]; a[2] = temp;

This works only because 5 and 3 are relatively prime. If they weren't, you'd have to execute the above G times with first taking the values 0, 1, .., G-1, where G is the GCD of the array length and the shift amount. (And the above works only for shift amounts > 0, but a shift amount < 0 can be dealt with by adding a.length to it.)

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1503964

Well, you need temporary storage of some description. If you have enough memory, you could do this in one go:

int[] buffer = new int[placesToShift];
// Save the start of the array in the buffer
System.arraycopy(array, 0, buffer, 0, placesToShift);
// Copy the rest of the array into place
System.arraycopy(array, placesToShift, array, 0, array.length - placesToShift);
// Copy the buffer into the end
System.arraycopy(buffer, 0, array, array.length - placesToShift, buffer.length);

It's also worth noting that you can always get by with at most half the array length as a buffer, by treating (say) a "shift left by 4" as a "shift right by 1".

You can do it with constant extra space by repeatedly shifting once. For example:

for (int i = 0; i < placesToShift; i++) {
    int firstElement = array[i];
    System.arraycopy(array, 1, array, 0, array.length - 1);
    array[array.length - 1] = firstElement;
}

That's inefficient in time of course, but efficient in space.

Upvotes: 3

OldCurmudgeon
OldCurmudgeon

Reputation: 65889

    int [] a = {1,2,3,4,5};
    int [] b = new int[a.length];
    Arrays.setAll(b, (int i) -> a[(i+3)%a.length]);
    System.out.println("a="+Arrays.toString(a));
    System.out.println("b="+Arrays.toString(b));

prints:

a=[1, 2, 3, 4, 5]
b=[4, 5, 1, 2, 3]

Upvotes: 2

Alexis C.
Alexis C.

Reputation: 93892

You could use Collections.rotate:

Integer[] arr = {1,2,3,4,5};
Collections.rotate(Arrays.asList(arr), -3);
System.out.println(Arrays.toString(arr));

Output:

[4, 5, 1, 2, 3]

Upvotes: 5

Related Questions