Komplexität des Entfernens von Duplikaten durch Verschieben von Elementen

Question

Der folgende Code versucht, Duplikate durch Überschreiben wiederholter Elemente aus einem sortierten Array zu entfernen. Obwohl es für Schleifen verschachtelt ist, ist seine Komplexität definitiv kleiner als O (n^2). Was wird die Komplexität des folgenden Codes sein?

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

Beginnen wir von der ersten Position aus. Es ist sicher nicht doppelt, also bewegst du dich nicht. Dann bewegen wir uns auf die zweite Position. Es kann vom ersten Positionswert kopiert werden, und dann kann es nicht sein. Wenn dies der Fall ist, müssen Sie es bis zum Ende verschieben. Für die ersten beiden Positionen haben Sie zwei Szenarien: eines bewegt sich nur durch das Array (es ist nicht doppelt vorhanden), das zweite ist das Element am Ende des Arrays erfordern Operationen von arr[j]=arr[j+1].

Jetzt, wenn wir den dritten Wert auf die zweite Position verschoben haben, sind wir noch dran (i-- Teil). Es kann ein Duplikat des ersten Wertes sein, und vielleicht ist es das nicht. Für die erste Option müssen Sie n-3 nehmen (seit Sie n-- getan haben, also bewegen Sie es von Position 2 zu Position n-1) Operationen von arr[j]=arr[j+1]. Wenn nun der zweite Wert kein Duplikat des ersten Wertes war (also nicht i-- und n--), aber der dritte Wert ist ein Duplikat von einem der ersten beiden Werte, müssen Sie noch n-3 Operationen von arr[j]=arr[j+1] (von Position 3 zur Position) ausführen n). So bleibt die Anzahl der Operationen in jedem Fall gleich.

Also haben wir hier ein Muster: n-2 + n-3 + n -4 + ... + 3 + 2 + 1 von Dingen herum bewegen. Diese Summe ist:

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

auf diese So basiert, da erste Teil durch Anordnung bewegt, die O(n) ist, die Komplexität dieses Algorithmus ist O(n^2). Worst-Case-Szenarien haben alle die gleichen Werte im Array.

Jetzt gibt es einen besseren Weg. Platziere alle Werte in Set. Dazu müssen Sie das Array durchlaufen (O(n)) und prüfen, ob sich etwas in Set befindet, also O(1). Nehmen Sie dann alle Ergebnisse von Set, und legen Sie sie in Array, das O(n) ist. Die Komplexität eines solchen Algorithmus ist O(n).