i***d
发帖数: 28 | 1 问一道老题，考古了但没有找到：
字符串有数字和字母，把数字放到字母的前面，但要保持原来的顺序。
例如: 1a2b3c==>123abc.
有没有比O(n^2)好的算法啊？ 谢谢！ |
e********r
发帖数: 2352 | 2 用两个List可以吗.
【在 i***d 的大作中提到】
: 问一道老题，考古了但没有找到：
: 字符串有数字和字母，把数字放到字母的前面，但要保持原来的顺序。
: 例如: 1a2b3c==>123abc.
: 有没有比O(n^2)好的算法啊？ 谢谢！
|
c***p
发帖数: 221 | 3 可以做到nlogn.
类似于merge sort.
【在 i***d 的大作中提到】
: 问一道老题，考古了但没有找到：
: 字符串有数字和字母，把数字放到字母的前面，但要保持原来的顺序。
: 例如: 1a2b3c==>123abc.
: 有没有比O(n^2)好的算法啊？ 谢谢！
|
p*****2
发帖数: 21240 | |
C***U
发帖数: 2406 | 5 恩 应该是可以O(n)的 但是空间要O(n)的吧？
【在 i***d 的大作中提到】
: 问一道老题，考古了但没有找到：
: 字符串有数字和字母，把数字放到字母的前面，但要保持原来的顺序。
: 例如: 1a2b3c==>123abc.
: 有没有比O(n^2)好的算法啊？ 谢谢！
|
i***d
发帖数: 28 | 6 印象中好像是要in-place的；
大拿们能不能讲讲思路啊， O(log(n)) 还是 O(n)？ |
c***p
发帖数: 221 | 7 这是个矩阵转置问题。可以做到O(n)，但要用到一些数学知识。
http://en.wikipedia.org/wiki/In-place_matrix_transposition
【在 i***d 的大作中提到】
: 印象中好像是要in-place的；
: 大拿们能不能讲讲思路啊， O(log(n)) 还是 O(n)？
|
e********r
发帖数: 2352 | 8 俺好像没有理解题，挨个数一下不就好了，就是O(n)，还是有额外的要求？
【在 i***d 的大作中提到】
: 印象中好像是要in-place的；
: 大拿们能不能讲讲思路啊， O(log(n)) 还是 O(n)？
|
t*********7
发帖数: 255 | 9 两个INDEX一个跟字母,一个跟数字,互换,应该O(N) |
p*i
发帖数: 411 | 10 你这个保持不了order吧
【在 t*********7 的大作中提到】
: 两个INDEX一个跟字母,一个跟数字,互换,应该O(N)
|
h**********l
发帖数: 6342 | 11 从最后走应该就可以了把
【在 p*i 的大作中提到】
: 你这个保持不了order吧
|
t*********7
发帖数: 255 | 12 除开互换字母跟数字,还要维护字母数字顺序,有点类似QUICK SORT吧...比如,1a2b3c走
到123bac的时候,数字INDEX在3,字母INDEX在B,RUN INDEX在a,那就互相ab...不过我没
验证这样到底行不行....只是凭感觉....
【在 p*i 的大作中提到】
: 你这个保持不了order吧
|
