删除和复制特定字符

给一个大小为n的字符数组，保存着一个字符串以'\0'结尾。这个n可能大于字符串长度，也就是说字符串后面还有一些可用空间。
现在要求删除所有的'#'，并且如果里面有'$'，那么就将其变为'$$'。如果最后的长度大于n，则抛出异常。
要求in place完成。

例子：
"ab#c$d"，n = 10
变为
"abc$$d"

想了好久没什么好想法，发上来求大神。

1. 遍历一遍 计算最后的长度n_1, 如果n_1>n 则抛出异常
2. 遍历一遍 in place删掉所有的#
3. 从右向左遍历 in place double所有的$

O(n) 不知道有没有常数优化

doveonthewing 发表于 2013-12-20 23:09
1. 遍历一遍 计算最后的长度n_1, 如果n_1>n 则抛出异常
2. 遍历一遍 in place删掉所有的#
3. 从右向左遍历 ...

有几个地方不明白……如何in place删掉所有的#？
是删除后将后面的向前移动，还是就放着不动了？
double $的时候，附近的空位不够如何做？

谢谢

OracleDesire 发表于 2013-12-21 09:32
有几个地方不明白……如何in place删掉所有的#？
是删除后将后面的向前移动，还是就放着不动了？
doubl ...

(1) 删除后把后面的向前移动
(2) 你已经知道n_1了 所以不会不够

doveonthewing 发表于 2013-12-21 10:07
(1) 删除后把后面的向前移动
(2) 你已经知道n_1了 所以不会不够

这是一个方法，但是这个方法复杂度太高，删除过程中无效的移来移去太多了，很可能不是面试时好的答案。
不知道还有没有什么高见？