Array rotation

Question

I'm trying to rotate an array so that, taking into account the number and array, it rotates the array by this amount. IE:

ABCDEFGH

given 3:

fghabcde

What is the best way to do this without using additional data structures / minimum space?

Here is the function title:

public static char[] rotateString(char[] s, int rotateAmount){ } 

Answer 1

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

If so, then the simplest solution is the best, since I do not need to bother with time optimization. I know that other solutions are much more elegant, I just posted them because I read the question as "make sure it is minimal in size."

 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 quickly cracked it. Basically, I just rotate in length until I rotate n number of times. To optimize it, you could probably take gcd(n, a.length) .

Now, since my solution is pretty terrible, I will 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 am assuming is a C-style implementation that works faster than mine, using a basic idea that with three changes allows for an inline shift.

As said here

The trick is to perform three feedback operations. One for the entire row, one from index 0 to k-1 and finally index k to n-1. Magically, this will give the correct spinning array without extra space! (Of course you need a temporary swap variable).

I have not tested this property on the blog I am associated with, so I will post it with a salt that seems to work, but I have never tested it myself ...

Answer 2

An implementation of Java Collections.rotate(List, int) can be found here ; it uses only fixed overhead, and it is pretty clean and easy to understand. I would not just call it (although with a wrapper such as Guava Chars.asList there would be only constant overhead), but the algorithm is neat and clean, and you can easily adapt it to your needs.

This is O(n) , but the reason is not entirely obvious; most of the work figures out why he will never visit any one index more than once. I will leave it as an exercise.

Answer 3

Something like that? temp requires additional O (1) storage. Try running this with shift=1 to see the idea behind it.

 public static String rotateString(char[] s, int rotateAmount) { int length = s.length; int shift = (length - rotateAmount) % length; for (int start = 0; start < gcd(length, shift); start++) { char temp = s[start]; for (int i = (start + shift)%length; i != start; i = (i + shift) % length) { s[(length + i - shift) % length] = s[i]; } s[(length + start - shift) % length] = temp; } return new String(s); } 

gcd(a,b) is the largest common denominator of a and b , and it can be calculated using, for example, the Euclidean algorithm .

The complexity of the time is O (n), where n is the length of the array.

Answer 4

• As you need to return an array of results, you still have to create it.

• The function should work in both directions and when there is one or several revolutions - like a rotation one number greater than the length of the array.

   public static char[] rotateString(char[] s, int rotateAmount){ int n=s.length; char[] res=new char[n]; if (n==0) return res; int turns=rotateAmount / n; int j=((-turns+1)*n+rotateAmount) % n; for (int i=0; i<n; i++){ if(j==n) j=0; res[j]=s[i]; j++; } return res; } 

verified by:

  System.out.println("'',+1->"+new String(rotateString("".toCharArray(),+1))); System.out.println("123,+1->"+new String(rotateString("123".toCharArray(),+1))); System.out.println("123,-1->"+new String(rotateString("123".toCharArray(),-1))); System.out.println("123,-5->"+new String(rotateString("123".toCharArray(),-5))); System.out.println("123,-6->"+new String(rotateString("123".toCharArray(),-6))); System.out.println("123,+6->"+new String(rotateString("123".toCharArray(),+6))); 

Answer 5

How about using stack?

Let me explain. When you press abcdefgh for the stack, it becomes hgfedcba

Now put one item at a time and add a line. suggests that the number of rotations is 3.

When you replenish the first element, you get h . Since 3 is less than the number of characters, popped pop is another element and add h . Therefore, when you add the next element, you get g . Prepare g to h . Thus, he becomes hg . Repeat the process for the amount of rotation (here it is 3), therefore, it will become fgh .

Now create a new line and pull the rest of the items from the stack and add each character. Therefore, it becomes " abcd ".

Combine the two lines. which is fghabcd .

Answer 6

Here is the C # version for reference only (you can refer to http://codingworkout.blogspot.com/2014/07/rotating-array.html for more information):

 void swap<T>(ref T x, ref T y) { T t = x; x = y; y = t; } void Reverse(int[] a, int start, int end) { int i = start, j = end; while (i < j) { swap<int>(ref a[i], ref a[j]); i++; j--; } } void Rotate(int[] a, int k) { a.ThrowIfNull("array"); k.Throw("k", e => e < 0); if (a.Length <= 1) { return; } k = k % a.Length; this.Reverse(a, 0, a.Length - 1); this.Reverse(a, 0, k - 1); this.Reverse(a, k, a.Length - 1); } 

Device tests

 [TestMethod] public void RotateTests() { int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; for (int i = 1; i <= a.Length; i++) { int k = a.Length - i + 1; int[] b = new int[a.Length]; this.Rotate(a, i); for(int j = 0;j<b.Length;j++) { if(k > a.Length) { k = (k % a.Length); } b[j] = k; k++; } for (int j = 0; j < a.Length;j++ ) { Assert.IsTrue(a[j] == b[j]); } this.Rotate(a, a.Length - i); } } 

Answer 7

I think it is easier and definitely faster.

 private static String rotate( char[] arrayStr, int K, int N ) { int[] my_array = new int[N]; for(int item = 0; item < N; item++) { my_array[(item+K) % N] = arrayStr[item]; } return my_array } 

where K = number of revolutions and N = length of the array

Answer 8

Try the following:

 public static char[] rotateString(char[] s, int rotateAmount){ String oldStr=new String(s); String newStr=oldStr.substring(oldStr.length()-rotateAmount,oldStr.length())+oldStr.substring(0,oldStr.length()-rotateAmount); return newStr.toCharArray(); }