为什么时间复杂度是 O(n) 却花了 54 毫秒

Question

我最近开始解决 leetcode 上的问题，并遇到了这个问题，我们必须从字符串中删除所有字母数字字符，然后检查该字符串是否是回文。 我试图保持 O(n) 时间复杂度，但仍然花费了 54 毫秒，这太长了，有人可以解释一下吗？这是代码：

class Solution {
public:
    bool isPalindrome(string s) {
        int n = 0;
        transform(s.begin(),s.end(),s.begin(),::tolower);
        while(s[n] != '\0'){
            if(isalnum(s[n]) == 0 ){
                s.erase(s.begin()+n);
            }
            else{
            n++;
            }
        }

        string check = s;
        reverse(s.begin(),s.end());

        if(s == check){
            return true;
        }
        else{
            return false;
        }

    }
};

我想知道代码的哪一部分精确地花费了时间

Answer 1

我想知道代码的哪一部分到底花费了时间

这是

erase

的呼唤。

引自docs：

由于向量使用数组作为底层存储，因此擦除向量末尾以外位置的元素会导致容器将段擦除后的所有元素重新定位到新位置。 这通常是一种低效的操作...

由于可能对多个索引进行此调用，因此您的算法的最坏时间情况复杂度为 O(n²)。