Java - Rotating Array

Java - Rotating array

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.

Rotating an array

Firstly, I will make a big assumption that "better" means "I do not want any/as few new data structures".

If this is the case, then the simplest solution is the best, since I don't need to bother optimising by time. I know that the other solutions are much more elegant, I've only posted it because I've read the question as "make sure it's minimal space-wise".

private static String rotate( final char[] a, final int n ) {
for(int i = 0; i < n; i++) {
char tmp = a[a.length-1];
for(int j = a.length-1; j >= 0; j--) {
a[j] = j == 0 ? tmp : a[(j-1+a.length)%a.length];
}
}
return new String(a);
}

So I hacked this out pretty quickly. Basically, I'm just doing rotates by lengths of one until I've rotated n number of times. To optimise it you probably could take gcd(n, a.length).

Now, since my solution is pretty terrible, I'll also post the following code taken from here

void reverse_string(char* str, int left, int right) {
char* p1 = str + left;
char* p2 = str + right;
while (p1 < p2) {
char temp = *p1;
*p1 = *p2;
*p2 = temp;
p1++;
p2--;
}
}

void rotate(char* str, int k) {
int n = strlen(str);
reverse_string(str, 0, n-1);
reverse_string(str, 0, k-1);
reverse_string(str, k, n-1);
}

This is, what I assume to be a C-style implementation that runs faster than mine, using a basic idea that with three reverses, you can implement an inline shift.

As is said here,

The trick is to do three reverse operation. One for the entire string, one from index 0 to k-1, and lastly index k to n-1. Magically, this will yield the correct rotated array, without any extra space! (Of course, you need a temporary variable for swapping).

I haven't verified this property on the blog I've linked to, so I will post it with a grain of salt that it would appear to work but I've never tested it myself...

rotate the elements of the given array k times to the right

Edit (from comments above): If i is 0, you're trying to get an index of -1 which will raise an ArrayOutOfBounds exception. If i starts from 1, then you're not dealing with the first number.

Here's the function you can use to rotate integers to the right:

public void rotate(int[] nums, int k) {
int arrLen = nums.length;

// If the number of times you want to rotate is bigger than the size of the array, get the minimum number of rotations to get the same result.
while (k > n) {
k = k - arrLen;
}
k = arrLen - k;
k = k % arrLen;
int i, m, n, temp;
int g_c_d = gcd(k, arrLen);
// Move the value in the i-th index
for (i = 0; i < g_c_d; i++) {
temp = arr[i];
m = i;
while (true) {
n = m + k;
if (n >= arrLen) {
n = n - arrLen;
}
if (n == i) {
break;
}
arr[m] = arr[n];
m = n;
}
arr[m] = temp;
}
}

// Find the greatest common divisor of two numbers, a and b
public void gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}

Let me briefly explain what it does. This is one of the most known algorithms: juggling. You divide the array into the n number of sets where n denotes the greatest common divisor of the length of the array and the number of times you want to rotate. Then, you move the numbers within sets.

This might be the most efficient in terms of time (as its time complexity is O(n)).

How can we rotate an array to the left?

Rotating to the left by n is the same as rotating to the right by length-n.

Rotate right (for positive n):

for(int i = 0; i < data.length; i++){
result[(i+n) % data.length ] = data[i];
}

Rotate left (for positive n):

for(int i = 0; i < data.length; i++){
result[(i+(data.length-n)) % data.length ] = data[i];
}

This way you can avoid a modulo of a negative number.

If you want to input an integer n that rotates right if n is positive and left if n is negative, you can do it like this:

 int[] rotateArray(int n, int[] data)
{
if(n < 0) // rotating left?
{
n = -n % data.length; // convert to +ve number specifying how
// many positions left to rotate & mod
n = data.length - n; // rotate left by n = rotate right by length - n
}
int[] result = new int[data.length];
for(int i = 0; i < data.length; i++){
result[(i+n) % data.length ] = data[i];
}
return result;
}

Rotate array and find index of maximum element

You can use following function. See it working here:

int[] rotate(int[] array, int[] rotate) 
{
int[] result = new int[rotate.length];
int index = 0;
int large = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > large) {
large = array[i];
index = i;
}
}
int len = array.length;
for (int i = 0; i < rotate.length; i++) {
int r = (index - (rotate[i]%len));
result[i] = (r>=0) ? r : (len+r);
}
return result;
}

Following is complete code:

class Test
{
static int[] rotate(int[] array, int[] rotate)
{
int[] result = new int[rotate.length];
int index = 0;
int large = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > large) {
large = array[i];
index = i;
}
}
int len = array.length;
for (int i = 0; i < rotate.length; i++) {
int r = (index - (rotate[i]%len));
result[i] = (r>=0) ? r : (len+r);
}
return result;
}

public static void main (String[] args) throws java.lang.Exception
{
int nums[] = {5,7,1,8,2};
int r[] = {2, 6, 5, 1, 2, 3, 4, 5, 0};

int res[] = rotate(nums, r);

for(int i=0; i<res.length; i++)
{
System.out.println(r[i] + " = "+ res[i]);
}
}
}

OUTPUT:

2 = 1
6 = 2
5 = 3
1 = 2
2 = 1
3 = 0
4 = 4
5 = 3
0 = 3


Related Topics



Leave a reply



Submit