要素をシフトすることによって重複を削除する複雑さ

Question

次のコードは、繰り返し要素を上書きすることによってソートされた配列から重複を削除しようとしています。それはループのために入れ子になっていますが、その複雑さはO（n^2）よりもはるかに少ないです。次のコードの複雑さはどのようになりますか？

int n = arr.length; 
    for(int i=0;i<n;i++){ 

     if(arr[i]==arr[i+1]){ 
      for(int j=i+1;j<n-1;j++){ 
       arr[j]=arr[j+1]; 
      } 
      n--; i--; 
     } 
    } 

Answer 1

最初の位置から開始します。それは確かに重複しないので、あなたは動いていません。その後、2番目の位置に移動します。最初の位置の値と重複している可能性があります。そうであれば、最後まで移動しなければならないので、最初の2つのポジションでは、2つのシナリオがあります.1つは配列全体を移動する（重複しない）、もう1つは配列の最後に要素を移動することです。 n-2の操作がarr[j]=arr[j+1]を必要とします。

ここで、3番目の値を2番目の位置に移動した場合、まだその上にいる（i--部分）。それは最初の価値と重複する可能性があり、そうでないかもしれない。最初のオプションの場合は、n--を実行したのでn-3とし、2の位置からn-1の位置に移動する必要があります。arr[j]=arr[j+1]です。今度は、2番目の値が最初の値と重複していない場合（i--とn--）、3番目の値が最初の2つの値のいずれかと重複している場合は、の操作をarr[j]=arr[j+1]（位置：3〜 n）。したがって、操作の数はそれぞれの場合に同じままです。

ここにはパターンがあります。n-2 + n-3 + n -4 + ... + 3 + 2 + 1のものが動き回っています。この合計は、次のとおり

n-2 + n-3 + n -4 + ... + 3 + 2 + 1 = n(n+1)/2 - n - n + 1 

最初の部分がO(n)ある配列を通って移動しているのでだからこれに基づいて、このアルゴリズムの複雑さはO(n^2)あります。最悪のシナリオでは配列内のすべての値が同じです。

今、良い方法があります。すべての値をSetに配置します。これには配列（O(n)）を移動し、何かがSetにあるかどうかを確認する必要があります。これはO(1)です。次に、すべての結果をSetから取り出し、配列に入れます。これはO(n)です。そのようなアルゴリズムの複雑さはO(n)です。