One of the classic problems with array is to perform in-place rotation on the array. For example, if we have an array of integers such as int[]array = new int[]{1, 2, 3, 4, 5, 6} and we want to rotate it around index 2, then the rotated array is {3, 4, 5, 6, 1, 2}. So, how can we rotate an array around a given index? Well here is the algorithm with explanation follows after:
Once we have the reverse function, the rotate function is trivial. rotateArrayByIndex does the three steps that we outlined above in order to rotate an input array by a specified index.
More and source - http://stackoverflow.com/questions/4457277/algorithm-to-rotate-an-array-in-linear-time
public void reverseArray(int[] array, int start, int end) { int i; int temp; while (start < end) { temp = array[start]; array[start] = array[end]; array[end] = temp; start++; end--; } } private static void rotateArrayByIndex(int array[], int rotatePos, int arraySize) { reverseArray(array, 0, rotatePos - 1); reverseArray(array, rotatePos, arraySize - 1); reverseArray(array, 0, arraySize - 1); }The strategy consists of three steps(consider the array - 1, 2, 3, 4, 5, 6).
- First, we reverse the first half of the array--starting from index 0 to (rotate index - 1).
rotateIndex = 2, hence array becomes = 2,1....3,4,5,6 - Then we reverse the second half of the array--starting from rotate index to the last index of the array. 2,1....6 5 4 3
- Lastly, we reverse the whole array.
3, 4, 5, 6, ...1,2
Once we have the reverse function, the rotate function is trivial. rotateArrayByIndex does the three steps that we outlined above in order to rotate an input array by a specified index.
More and source - http://stackoverflow.com/questions/4457277/algorithm-to-rotate-an-array-in-linear-time
0 comments:
Post a Comment