更正式地说,让str
为有问题的字符串,让其长度为l
。我知道可以使用substr
函数轻松完成上述操作:
str.substr(1)
str.substr(0,l-1)
但是根据this页面,上述方法在
O(l)
中这样做。有没有办法在
O(1)
中实现相同的目的?编辑:在将此问题标记为重复之前,请注意,我要求使用 O(1)实现来删除字符串的终端字符。这个问题似乎与该问题的答案都没有一个可以做出任何努力来回答这个问题,显然是因为那个问题并没有要求。
最佳答案
substr
函数不会删除字符。您在该函数上调用的字符串不会被修改,因此所有字符均保持不变。但是,调用它来选择一个除结束符之外的所有字符的子字符串所需的时间将是O(n),因为它涉及到复制所有其他字符。
从字符串中删除字符所需的时间在于转移所有后续字符以替换已删除的字符,这与substr
中的复制非常相似。字符串中通常有n个字符,因此删除任意字符的复杂度为O(n)。
没有固定时间的方法来删除任意长度的字符串的第一个字符。从字符串末尾删除固定数目的字符C的字符可以在固定时间内完成,因此删除最后一个字符(C = 0)为O(1)。
如果您经常需要从序列的末端添加或删除元素,则可以考虑更适合该操作的数据结构。 list
和deque
都很好。
关于c++ - 如何在O(1)的C++中从 'string'中删除终止符?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14959206/