转换 a1b2c3d4.. 到 abcd1234.. 要求O（n）time, in place.

本题是: An in-place algorithm for String Transformation".

根据上面链结, 基本解法为:

1. Cut out the largest prefix sub-string of size of the form 3^k + 1. In this step, we find the largest non-negative integer k such that 3^k+1 is smaller than or equal to n (length of string)

2. Apply cycle leader iteration algorithm ( it has been discussed below ), starting with index 1, 3, 9…… to this sub-string. Cycle leader iteration algorithm moves all the items of this sub-string to their correct positions, i.e. all the alphabets are shifted to the left half of the sub-string and all the digits are shifted to the right half of this sub-string.

3. Process the remaining sub-string recursively using steps#1 and #2.

4. Now, we only need to join the processed sub-strings together. Start from any end ( say from left ), pick two sub-strings and apply the below steps:

….4.1 Reverse the second half of first sub-string.
….4.2 Reverse the first half of second sub-string.
….4.3 Reverse the second half of first sub-string and first half of second sub-string together.

5. Repeat step#4 until all sub-strings are joined. It is similar to k-way merging where first sub-string is joined with second. The resultant is merged with third and so on.

Cycle leader iteration algorithm:


    if( oldIndex is odd )
        newIndex = len / 2 + oldIndex / 2;
    else
        newIndex = oldIndex / 2;


看来关键在于, 长度为3^k + 1的数组可以应用in place cycle leader iteration algorithm.

此问题的逆问题: 

Given an array [a1, a2, ..., an, b1, b2, ..., bn], transform it to [a1, b1, a2, b2, ..., an, bn].

Requirement: time complexity O(nlogn), space complexity O(logn)

Sol: the base idea is to use quicksort techniques. Suppose the current array is A, whose size is 2k.

1. Divide A into four segments: A = [A1 A2 B1 B2], where A1.size = B1.size = k / 2, B1.size = B2.size = k - k / 2;
2. Swap A2 and B1, and we get A = [A1 B1 A2 B2]. In this step, we actually need to rotate [A2 B1] to the right by k - k / 2 items. This can be done by reversing [A2 B1] first, and then reversing [A2] and [B1] respectively.
3. Recursive on [A1 B1] and [A2 B2] respectively.

Example: A = [1 2 3 4 5 6 7 8 9 10]
A1 = [1 2], A2 = [3 4 5], B1 = [6 7], B2 = [8 9 10]
After 2nd step, A = [1 2 | 6 7 | 3 4 5| 8 9 10]
For the 3rd step, process [1 2 6 7] and [3 4 5 8 9 10] respectively

--

本文来自: http://www.mitbbs.com/article_t/JobHunting/32568289.html