c++ - 从字符串中删除一个字符

Question

我想编写一段代码，从字符串中删除给定的字符。我想出了以下代码段。

现在，虽然这完成了我的工作，但它给了我 O(n^2) 的最坏情况复杂度。谁能帮我改进一下。

#include<iostream.h>
#include<conio.h>
#include<stdio.h>

void Push(char *, int i);

int n=6;

int main()
{
 clrscr();
 char *p = "helelo";
 char delChar = 'e';

 for(int i=0;i<5;i++)
 {
  if(*(p + i) == delChar)
  {
   Push(p, i);
  }
 }
 cout<<p<<endl;
 getch();
 return 1;
}

void Push(char *p, int i)
{
 for(int k=i;k<n;k++)
 {
  *(p + k) = *(p+k+1);
 }
}

谢谢

Answer 1

#include <cstring>
#include <algorithm>
#include <iostream>

int main() {
  using namespace std;

  char s[] = "helelo";
  cout << s << '\n';

  char *end = s + strlen(s);
  end = remove(s, end, 'e');
  *end = '\0';
  cout << s << '\n';  // hllo

  return 0;
}

请注意，您不能修改字符串文字，所以我使用了一个字符数组。 std::string 会更容易。

如果您想了解 std::remove 的工作原理，char* 实例化(因为它是一个模板)为了简单起见看起来像这样:

char* remove(char *begin, char *end, char value) {
  char *next = begin;
  for (; begin != end; ++begin) {
    if (*begin != value) {
      *next++ = *begin;
    }
  }
  return next;
}