0

这是来自“破解编码面试”Q1.3 的问题“设计一种算法并编写代码以在不使用任何额外缓冲区的情况下删除字符串中的重复字符。注意:一个或两个额外的变量很好。一份额外的副本数组不是。” 我编写了一个似乎运行良好的程序,但我对自己的程序感到困惑。这是附加的代码。

string remove_duplicates(string &s1)
{
   int n=s1.size();
   for(int i=n-1; i!=-1; --i)
        for(int j=0; j<i; ++j)
        {
            if(s1[i]==s1[j])
            {
                int k=i;
                while(k!=n)
                {
                    s1[k]=s1[k+1];
                    k++;
                }
            }
        }
    return s1;
}

如果 s1=abcdeafg,使用此代码输出将是 abcdefg,(如果输入是 abababab,输出将是 ab)但我的想法是因为 s1 的长度没有改变,所以输出应该是 abcdefga,因为我只是将第二个“a”移动到 s1 的末尾。大家能帮我解释一下吗?

4

1 回答 1

2

s1 的长度实际上是在变化的。当您找到重复字符并使用 while(k!=n) 循环将重复字符移向 s1 的末尾时,在循环的最后一次迭代中,当 k == n-1 时,代码正在评估 s1[ n-1] = s1[n] 实际上是 s1[n-1] = '\0',所以 s1 的长度缩短了 1。

于 2012-07-21T22:14:25.263 回答