Bester Algorithmus zum Löschen von Duplikaten in einem Array von Zeichenketten

Question

Heute in der Schule hat uns der Lehrer gebeten, einen Algorithmus zur Löschung von Duplikaten zu entwickeln. Das ist gar nicht so schwierig, und alle haben die folgende Lösung gefunden (Pseudocode):

for i from 1 to n - 1
    for j from i + 1 to n
        if v[i] == v[j] then remove(v, v[j])    // remove(from, what)
    next j
next i

Der Rechenaufwand für dieses Algo beträgt n(n-1)/2 . (Wir sind in der High School und haben noch nicht über Big-O gesprochen, aber es scheint zu sein O(n^2) ). Diese Lösung sieht hässlich aus und ist natürlich langsam, also habe ich versucht, etwas Schnelleres zu programmieren:

procedure binarySearch(vector, element, *position)
    // this procedure searches for element in vector, returning
    // true if found, false otherwise. *position will contain the
    // element's place (where it is or where it should be)
end procedure

----

// same type as v
vS = new array[n]

for i from 1 to n - 1
    if binarySearch(vS, v[i], &p) = true then
        remove(v, v[i])
    else
        add(vS, v[i], p)      // adds v[i] in position p of array vS
    end if
next i

Auf diese Weise vS enthält alle Elemente, die wir bereits übergeben haben. Wenn Element v[i] in diesem Array ist, dann ist es ein Duplikat und wird entfernt. Der Rechenaufwand für die binäre Suche ist log(n) und für die Hauptschleife (zweites Snippet) ist n . Daher ist das gesamte CC n*log(n) wenn ich mich nicht irre.

Dann hatte ich eine andere Idee, einen binären Baum zu verwenden, aber ich kann sie nicht festhalten.
Meine Fragen lauten im Wesentlichen:

• Ist meine CC-Berechnung richtig? (und, falls nicht, warum?)
• Gibt es dafür eine schnellere Methode?

感謝