Java - Rotating array
So the goal is to rotate the elements in an array right a
times.
As an example; if a==2
, then array = {0,1,2,3,4}
would become array = {3,4,0,1,2}
Here's what I have:
for (int x = 0; x <= array.length-1; x++){
array[x+a] = array[x];
}
However, this fails to account for when [x+a]
is greater than the length of the array. I read that I should store the ones that are greater in a different Array but seeing as a
is variable I'm not sure that's the best solution.
Thanks in advance.
Solution 1:
Add a modulo array length to your code:
// create a newArray before of the same size as array
// copy
for(int x = 0; x <= array.length-1; x++){
newArray[(x+a) % array.length ] = array[x];
}
You should also create a new Array
to copy to, so you do not overwrite values, that you'll need later on.
Solution 2:
In case you don't want to reinvent the wheel (maybe it's an exercise but it can be good to know), you can use Collections.rotate
.
Be aware that it requires an array of objects, not primitive data type (otherwise you'll swap arrays themselves in the list).
Integer[] arr = {0,1,2,3,4};
Collections.rotate(Arrays.asList(arr), 2);
System.out.println(Arrays.toString(arr)); //[3, 4, 0, 1, 2]
Solution 3:
Arraycopy is an expensive operation, both time and memory wise. Following would be an efficient way to rotate array without using extra space (unlike the accepted answer where a new array is created of the same size).
public void rotate(int[] nums, int k) { // k = 2
k %= nums.length;
// {0,1,2,3,4}
reverse(nums, 0, nums.length - 1); // Reverse the whole Array
// {4,3,2,1,0}
reverse(nums, 0, k - 1); // Reverse first part (4,3 -> 3,4)
// {3,4,2,1,0}
reverse(nums, k, nums.length - 1); //Reverse second part (2,1,0 -> 0,1,2)
// {3,4,0,1,2}
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}