Algorithmus: effiziente Möglichkeit, doppelte Ganzzahlen aus einem Array zu entfernen

Ich habe dieses Problem aus einem Interview mit Microsoft.

Schreiben Sie bei einem gegebenen Array zufälliger Ganzzahlen einen Algorithmus in C, der doppelte Zahlen entfernt und die eindeutigen Zahlen im ursprünglichen Array zurückgibt.

B. Eingang: {4, 8, 4, 1, 1, 2, 9} Ausgabe: {4, 8, 1, 2, 9, ?, ?}

Eine Einschränkung ist, dass der erwartete Algorithmus nicht erfordern sollte, dass das Array zuerst sortiert wird. Und wenn ein Element entfernt wurde, müssen die folgenden Elemente ebenfalls nach vorne verschoben werden. Wie auch immer, der Wert der Elemente am Ende des Arrays, wo Elemente nach vorne verschoben wurden, ist vernachlässigbar.

Aktualisieren: Das Ergebnis muss im ursprünglichen Array zurückgegeben werden und Hilfsdatenstrukturen (z. B. Hashtable) sollten nicht verwendet werden. Ich denke jedoch, dass die Auftragserhaltung nicht erforderlich ist.

Update2: Für diejenigen, die sich fragen, warum diese unpraktischen Einschränkungen vorliegen, dies war eine Interviewfrage, und all diese Einschränkungen werden während des Denkprozesses diskutiert, um zu sehen, wie ich auf andere Ideen kommen kann.

Ich habe das schon einmal auf SO gepostet, aber ich werde es hier wiedergeben, weil es ziemlich cool ist. Es verwendet Hashing und baut so etwas wie ein Hash-Set auf. Es ist garantiert O (1) im Achselraum (die Rekursion ist ein Tail Call) und ist typischerweise O (N) Zeitkomplexität. Der Algorithmus ist wie folgt:

1. Nehmen Sie das erste Element des Arrays, dies wird der Wächter sein.
2. Ordnen Sie den Rest des Arrays so weit wie möglich neu an, sodass sich jedes Element an der Position befindet, die seinem Hash entspricht. Wenn dieser Schritt abgeschlossen ist, werden Duplikate entdeckt. Setzen Sie sie gleich Sentinel.
3. Verschieben Sie alle Elemente, deren Index gleich dem Hash ist, an den Anfang des Arrays.
4. Verschieben Sie alle Elemente, die Sentinel entsprechen, mit Ausnahme des ersten Elements des Arrays, an das Ende des Arrays.
5. Was zwischen den richtig gehashten Elementen und den doppelten Elementen übrig bleibt, sind die Elemente, die aufgrund einer Kollision nicht in den Index platziert werden konnten, der ihrem Hash entspricht. Rekurs, um mit diesen Elementen umzugehen.

Dies kann als O(N) gezeigt werden, sofern kein pathologisches Szenario im Hashing vorliegt: Auch wenn es keine Duplikate gibt, werden bei jeder Rekursion ungefähr 2/3 der Elemente eliminiert. Jede Rekursionsebene ist O(n), wobei klein n die Menge der verbleibenden Elemente ist. Das einzige Problem ist, dass es in der Praxis langsamer ist als eine schnelle Sortierung, wenn es wenige Duplikate gibt, dh viele Kollisionen. Wenn es jedoch große Mengen an Duplikaten gibt, ist es erstaunlich schnell.

Bearbeiten: In aktuellen Implementierungen von D ist hash_t 32 Bit. Alles an diesem Algorithmus geht davon aus, dass es im vollen 32-Bit-Raum, wenn überhaupt, nur sehr wenige Hash-Kollisionen geben wird. Kollisionen können jedoch häufig im Modulraum auftreten. Diese Annahme wird jedoch aller Wahrscheinlichkeit nach für jeden vernünftig großen Datensatz zutreffen. Wenn der Schlüssel kleiner oder gleich 32 Bit ist, kann es sich um einen eigenen Hash handeln, was bedeutet, dass eine Kollision im vollen 32-Bit-Raum unmöglich ist. Wenn es größer ist, können Sie einfach nicht genug davon in den 32-Bit-Adressraum des Speichers stecken, damit dies ein Problem darstellt. Ich gehe davon aus, dass hash_t in 64-Bit-Implementierungen von D auf 64 Bit erhöht wird, wo Datensätze größer sein können. Sollte sich dies jemals als Problem erweisen, könnte man außerdem die Hash-Funktion auf jeder Rekursionsebene ändern.

Hier ist eine Implementierung in der Programmiersprache D:

void uniqueInPlace(T)(ref T[] dataIn) {
    uniqueInPlaceImpl(dataIn, 0);
}

void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
    if(dataIn.length - start < 2)
        return;

    invariant T sentinel = dataIn[start];
    T[] data = dataIn[start + 1..$];

    static hash_t getHash(T elem) {
        static if(is(T == uint) || is(T == int)) {
            return cast(hash_t) elem;
        } else static if(__traits(compiles, elem.toHash)) {
            return elem.toHash;
        } else {
            static auto ti = typeid(typeof(elem));
            return ti.getHash(&elem);
        }
    }

    for(size_t index = 0; index < data.length;) {
        if(data[index] == sentinel) {
            index++;
            continue;
        }

        auto hash = getHash(data[index]) % data.length;
        if(index == hash) {
            index++;
            continue;
        }

        if(data[index] == data[hash]) {
            data[index] = sentinel;
            index++;
            continue;
        }

        if(data[hash] == sentinel) {
            swap(data[hash], data[index]);
            index++;
            continue;
        }

        auto hashHash = getHash(data[hash]) % data.length;
        if(hashHash != hash) {
            swap(data[index], data[hash]);
            if(hash < index)
                index++;
        } else {
            index++;
        }
    }


    size_t swapPos = 0;
    foreach(i; 0..data.length) {
        if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
            swap(data[i], data[swapPos++]);
        }
    }

    size_t sentinelPos = data.length;
    for(size_t i = swapPos; i < sentinelPos;) {
        if(data[i] == sentinel) {
            swap(data[i], data[--sentinelPos]);
        } else {
            i++;
        }
    }

    dataIn = dataIn[0..sentinelPos + start + 1];
    uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}

Wenn Sie nach der überlegenen O-Notation suchen, ist das Sortieren des Arrays mit einer O(n log n)-Sortierung und dann eine O(n)-Traversierung möglicherweise die beste Route. Ohne Sortierung sehen Sie O(n^2).

Bearbeiten: Wenn Sie nur Ganzzahlen ausführen, können Sie auch eine Radix-Sortierung durchführen, um O (n) zu erhalten.

Eine weitere effiziente Implementierung

int i, j;

/* new length of modified array */
int NewLength = 1;

for(i=1; i< Length; i++){

   for(j=0; j< NewLength ; j++)
   {

      if(array[i] == array[j])
      break;
   }

   /* if none of the values in index[0..j] of array is not same as array[i],
      then copy the current value to corresponding new position in array */

  if (j==NewLength )
      array[NewLength++] = array[i];
}

Bei dieser Implementierung besteht keine Notwendigkeit, das Array zu sortieren. Auch wenn ein doppeltes Element gefunden wird, müssen nicht alle Elemente danach um eine Position verschoben werden.

Die Ausgabe dieses Codes ist ein Array[] mit Größe NewLength

Hier beginnen wir mit dem 2. Element im Array und vergleichen es mit allen Elementen im Array bis zu diesem Array. Wir halten eine zusätzliche Indexvariable ‘NewLength’ zum Ändern des Eingabearrays bereit. Die Variable NewLength wird auf 0 initialisiert.

Element im Array[1] wird mit array verglichen[0]. Wenn sie unterschiedlich sind, dann Wert im Array[NewLength] wird mit Array modifiziert[1] und erhöhen Sie NewLength. Wenn sie gleich sind, wird NewLength nicht geändert.

Also, wenn wir ein Array haben [1 2 1 3 1]dann

Im ersten Durchgang der ‘j’-Schleife, Array[1] (2) wird mit array0 verglichen, dann wird 2 in array geschrieben[NewLength] = Reihe[1]
so wird Array sein [1 2] da NewLength = 2

Im zweiten Durchgang der ‘j’-Schleife, Array[2] (1) wird mit array0 und array1 verglichen. Hier seit Array[2] (1) und array0 sind die gleiche Schleife, die hier unterbrochen wird. so wird Array sein [1 2] da NewLength = 2

usw

1. Verwendung von O(1) zusätzlichem Speicherplatz in O(n log n) Zeit

Dies ist zum Beispiel möglich:

• Führen Sie zuerst eine direkte O(n log n)-Sortierung durch
• Gehen Sie dann einmal durch die Liste und schreiben Sie die erste Instanz von every zurück an den Anfang der Liste

Ich glaube, der Partner von ejel hat Recht, dass der beste Weg, dies zu tun, eine direkte Zusammenführungssortierung mit einem vereinfachten Zusammenführungsschritt wäre, und dass dies wahrscheinlich die Absicht der Frage ist, wenn Sie z. Schreiben einer neuen Bibliotheksfunktion, um dies so effizient wie möglich zu tun, ohne die Eingaben verbessern zu können, und es gibt Fälle, in denen es nützlich wäre, dies ohne eine Hash-Tabelle zu tun, abhängig von der Art der Eingaben. Das habe ich aber nicht wirklich überprüft.

2. Verwendung von O(lots) zusätzlichem Platz in O(n) Zeit

• Deklarieren Sie ein Array mit Nullen, das groß genug ist, um alle Ganzzahlen aufzunehmen
• Gehen Sie einmal durch das Array
• Setzen Sie das entsprechende Array-Element für jede Ganzzahl auf 1.
• Wenn es bereits 1 war, überspringen Sie diese Ganzzahl.

Dies funktioniert nur, wenn mehrere fragwürdige Annahmen gelten:

• Es ist möglich, Speicher billig zu nullen, oder die Größe der Ints ist klein im Vergleich zu ihrer Anzahl
• Sie können Ihr Betriebssystem gerne nach 256^sizepof(int) Speicher fragen
• und es wird es wirklich sehr effizient für Sie zwischenspeichern, wenn es riesig ist

Es ist eine schlechte Antwort, aber wenn Sie VIELE Eingabeelemente haben, die jedoch alle 8-Bit-Ganzzahlen (oder vielleicht sogar 16-Bit-Ganzzahlen) sind, könnte dies der beste Weg sein.

3. O(wenig)-ish zusätzlicher Raum, O(n)-ish-Zeit

Wie #2, aber verwenden Sie eine Hash-Tabelle.

4. Der klare Weg

Wenn die Anzahl der Elemente klein ist, ist das Schreiben eines geeigneten Algorithmus nicht sinnvoll, wenn anderer Code schneller zu schreiben und schneller zu lesen ist.

Z.B. Gehen Sie durch das Array für jedes eindeutige Element (dh das erste Element, das zweite Element (Duplikate des ersten wurden entfernt) usw.) und entfernen Sie alle identischen Elemente. O(1) zusätzlicher Raum, O(n^2) Zeit.

Z.B. Verwenden Sie Bibliotheksfunktionen, die dies tun. Effizienz hängt davon ab, was Sie leicht zur Verfügung haben.