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

多次元配列は、実際には変装した 1 次元配列であるため、これを行うことができます。O(1)ただし、スペース要件を満たすために、これをインプレースで行う必要があります。幸いなことに、これはよく知られている問題であり、いくつかのアプローチが考えられます。