1

更正式地说，设str为有问题的字符串，设其长度为l。我知道使用以下substr功能可以轻松完成上述操作：

  • 删除第一个字符 -str.substr(1)
  • 删除最后一个字符 -str.substr(0,l-1)

但根据this page，上述方法在O(l).

有没有办法达到同样的效果O(1)？

编辑：在将此问题标记为重复之前，请注意我要求使用O(1)实现来删除字符串的终端字符。这个问题的答案似乎与这个问题的重复，没有一个答案会做出任何努力来回答这个问题，显然是因为这个问题并没有要求它。

4

3 回答 3

2

我不知道实际保证这一点的标准，但可以合理地假设：

str.resize(str.length() - 1);

是 O(1)。如果假设对您的情况不够好，您可以编写自己的字符串类。只要确保你在编写一个好的字符串类上所付出的努力值得 O(1) 保证来删除最后一个字符。

于 2013-02-19T14:28:30.430 回答
2

该substr函数不会删除字符。您调用该函数的字符串不会被修改，因此所有字符都保持不变。尽管如此，调用它来选择一个包含除终结符之外的所有字符的子字符串所需的时间将是 O( n )，因为它涉及复制所有其他字符。

从字符串中删除一个字符所需的时间在于移动所有后续字符以替换已删除的字符，就像在substr. 字符串中一般有n 个字符，因此删除任意字符的复杂度为 O( n )。

没有固定时间的方法来删除任意长度字符串的第一个字符。从字符串末尾删除固定数量的字符C的字符可以在恒定时间内完成，因此删除最后一个字符 ( C = 0) 是 O(1)。

如果您经常需要从序列的末端添加或删除元素，您可能会考虑更适合该操作的数据结构。两者list都deque有好处。

于 2013-02-19T14:38:42.743 回答
0

要std::string在 O(1) 时间内删除 a 的最后一个字符，

您可以resize将字符串向下移动 1 个单位。

如果您想要一个表达式结果（不修改原始字符串），您将不得不使用其他类而不是std::string. 一对迭代器会做得很好。

于 2013-02-19T14:26:19.293 回答