Given
an array, rotate it to the right by 'k' positions. For example, given
an input array A = {1,2,3,4,5,6} and k = 4, the rotated array is
{5,6,1,2,3,4}.
A
straight-forward method is to have a new array R of the same size as
A. Starting from the index k, copy all the elements from A to R. Then
copy the elements between the indexes 0 and k-1 in A to R. This
approach uses O(n) additional space.
To
rotate an array in-place, we need to perform a sequence of in-place
reversal operations.
Given
A = {1,2,3,4,5,6} and k = 4, perform the following reversals:
Step
1: Reverse the elements between indexes 0 and k-1 in-place
-
432156
Step
2: Reverse the elements between indexes k and n-1 in-place, where n
is the size of A
-
432165
Step 3: Reverse
the entire array (between 0 and n-1) in-place
-
561234
The outcome of
the step 3 is the rotated array.
The time
complexity of this method is O(n) with no additional space required.
Here is the C++ code:
int
a[] = {1,2,3,4,5,6};
int
size = 6;
void
Rotate(int
index) {
Reverse(0,index-1);
Reverse(index,size-1);
Reverse(0,size-1);
Print();
}
void
Reverse(int
begin, int
end) {
if(begin
< 0 || end >= size) {
return;
}
for(int
i = begin, j = end; i <= j; ++i, --j) {
int
tmp;
tmp
= a[i];
a[i]
= a[j];
a[j]
= tmp;
}
}
void
Print()
{
for(int
i = 0; i < size; ++i) {
cout
<< a[i] << " ";
}
}
This
method does 2n swaps in all. There is a different divide-and-conquer
approach which can be used to get an algorithm that does the rotate
in n swaps. I will try to discuss that in a future post.
No comments:
Post a Comment