algorithm - 按字符的一半重新排序字符串

Question

这是一道面试题。

Given a string such as: 123456abcdef consisting of n/2 integers followed by n/2 characters. Reorder the string to contain as 1a2b3c4d5e6f . The algortithm should be in-place.

我给出的解决方案很简单 - O(n^2)。只需将字符向左移动 n/2 个位置。

我尝试使用递归作为 -
A。将第一部分的后半部分与第二部分的前半部分交换 - 例如
123 456 abc def
123 abc 456 def
b.递归两半。

我卡住的 pbm 是交换随着元素的数量而变化 - 例如。

接下来要做什么？ 第123章 12ab 3c

要做什么:12345 abcde 123abc 45ab

这是一个很老的问题，可能是重复的。请让我知道.. :)

另一个例子: 输入:38726zfgsa 输出:3z8f7g2s6a

Answer 1

以下是我解决问题的方法:

1) Divide the string into two partitions, number part and letter part
2) Divide each of those partitions into two more (equal sized)
3) Swap the second the third partition (inner number and inner letter)
4) Recurse on the original two partitions (with their newly swapped bits)
5) Stop when the partition has a size of 2

例如:

123456abcdef -> 123456 abcdef -> 123 456 abc def -> 123 abc 456 def

123abc -> 123 abc -> 12 3 ab c -> 12 ab 3 c

12 ab -> 1 2 a b -> 1 a 2 b

...等等

对于递归的另一半也是如此..

所有这些都可以就地完成，唯一的问题是交换大小不同的分区(但它会相差一个，所以不难处理)。