string - 将字符串从 a1b2c3d4 转换为 abcd1234

Question

我得到一个包含数字和字母的字符串。数字占据all odd positions and letters even positions。我需要转换这个字符串，使所有字母都移动到数组的前面，所有数字都在最后。

需要保留字母和数字的相对顺序

I need to do this in O(n) time and O(1) space.

例如：a1b2c3d4 -> abcd1234 , x3y4z6 -> xyz346

这 previous question有一个解释算法，但无论我多么努力，我都无法掌握它。

我希望有人可以通过示例测试用例向我解释这一点。

Answer 1

关键是将输入数组视为这样的矩阵：

a 1
b 2
c 3
d 4

并意识到你想要这个矩阵的转置

a b c d
1 2 3 4

请记住，多维数组实际上只是变相的一维数组，因此您可以这样做。但是您需要就地执行此操作以满足O(1)空间要求。幸运的是，这是一个众所周知的问题，有几种可能的方法。