c++ - 获取时间复杂度错误

Question

我正在尝试解决这个问题:https://www.interviewbit.com/problems/add-one-to-number但我总是得到

Time Complexity Error :

Runtime Error. Your submission stopped because of a runtime error. ex:division by zero, array index out of bounds, uncaught exception Youcan try testing your code with custom input and try putting debugstatements in your code.

谁能告诉我我的解决方案有什么问题？

vector<int> Solution::plusOne(vector<int> &A) {
    vector<int> res;
    int rem=1;
    while(A[0]==0 && A.size()>1){
        A.erase(A.begin());
    }
    for(vector<int>::reverse_iterator it=A.rbegin();it!=A.rend();++it){
        int t = *it;
        t=t+rem;
        res.insert(res.begin(), t%10);
        rem = t/10;
    }
    while(rem!=0){
        res.insert(res.begin(), rem);
        rem/=10;
    }
    
    return res;
}

Answer 1

您的解决方案失败，因为计算时间过长。在 vector 的开头删除和插入是非常昂贵的。例如，如果输入 vector 的开头有一百万个零，而你循环遍历并使用删除来删除每个零，这将花费很长时间，因为 vector 每次都需要重新创建自己减去第一个元素。答案是找到一种方法来进行计算，同时尽可能少地修改 vector 。

编辑:也有可能 interviewbit 正在跟踪计算时间的尺度。例如，如果一个解决方案的时间复杂度为 O(N^2)，而正确的解决方案的时间复杂度为 O(N) 或 O( 1) 那么这就是时间复杂度错误的定义。 O(N^2) 的解决方案对于大小为 n 的输入可能需要 4 毫秒，对于大小为 2n 的输入可能需要 16 毫秒。如果他们期望线性或恒定的时间复杂度，那么解决方案就会失败。