時間計算エラー

Question

を取得、私はこの質問を解決しようとしています：https://www.interviewbit.com/problems/add-one-to-number をしかし、私はいつも

時間計算エラー取得しています：

ランタイムエラーを。実行時エラーのために送信が停止しました。例： ゼロ除算、配列インデックスが範囲外、キャッチされない例外 は、カスタム入力でコードをテストし、コードにデバッグ ステートメントを入れてみることができます。

誰も私の解決策に間違っていると教えてもらえますか？

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

解決に時間がかかりすぎて解決できません。ベクトルの始めに消去して挿入するのは非常に高価です。例えば、最初に入力ベクトルに百万のゼロがあり、ループして消去を使用してそれぞれを削除すると、ベクトルが最初の要素を引いたときにそれ自身を再作成する必要があるため、実際には長い時間がかかります。答えは、ベクトルをできるだけ小さく変更しながら計算を行う方法を見つけることです。

編集： interviewbitは計算時間のスケールを追跡することもできます。例えば、解がO(N^2)の時間複雑さを有し、正しい解がO(N)またはO(1)の時間複雑度を有する場合、それは時間複雑度エラーの定義である。 O(N^2)の解決策は、サイズnの入力に対しては4ms、サイズ2nの入力に対しては16msかかることがある。線形または一定の時間の複雑さが予想される場合、その解決策は失敗する。