搜索此博客

2011年2月28日星期一

函数将字符串中的字符'*'移到串的前部分, 前面的非'*'字符后移,但不能改变非'*'字符的先后顺序,函数返回串中字符'*'的数量。

如原始串为:ab**cd**e*12,
处理后为*****abcde12,函数并返回值为5。(要求使用尽量少的时间和辅助空间)

这个题需要用到两个额外的下标而且要从后往前查找:第二个下标先找到第一个‘*’的位置,第一个下标,找到第一个'*'后面的字母,交换其中的字母;然后第二个下标指向下一个字符,第一个下标找到下一个字母,继续交换。
Time: O(n)

没有评论:

发表评论