Algorithmus: Effiziente Methode zum Entfernen doppelter Ganzzahlen aus einem Array

92

Ich habe dieses Problem durch ein Interview mit Microsoft erhalten.

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

ZB Eingabe: {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 auch die folgenden Elemente nach vorne verschoben werden. Auf jeden Fall ist der Wert der Elemente am Ende des Arrays, bei dem die Elemente nach vorne verschoben wurden, vernachlässigbar.

Update: Das Ergebnis muss im ursprünglichen Array zurückgegeben werden und die Hilfsdatenstruktur (z. B. Hashtabelle) sollte nicht verwendet werden. Ich denke jedoch, dass eine Auftragserhaltung nicht erforderlich ist.

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

Ejel
quelle
4
Müssen Sie die Reihenfolge der eindeutigen Nummern beibehalten?
Douglas Leeder
1
Muss das Ergebnis im ursprünglichen Array zurückgegeben werden?
Douglas Leeder
1
Ich habe die Frage aktualisiert. Das Ergebnis sollte im ursprünglichen Array zurückgegeben werden. Die Reihenfolge der Sequenz spielt jedoch keine Rolle.
Ejel
3
Es ist ziemlich ärgerlich, wenn jemand seine Antwort auf die Frage und andere Antworten pimpt. Sei einfach geduldig, die Leute werden dorthin gelangen.
GManNickG
2
Warum ist eine Hashtabelle nicht erlaubt? Diese Einschränkung macht keinen Sinn.
RBarryYoung

Antworten:

19

Wie wäre es mit:

void rmdup(int *array, int length)
{
    int *current , *end = array + length - 1;

    for ( current = array + 1; array < end; array++, current = array + 1 )
    {
        while ( current <= end )
        {
            if ( *current == *array )
            {
                *current = *end--;
            }
            else
            {
                current++;
            }
        }
    }
}

Sollte O (n ^ 2) oder weniger sein.

mocj
quelle
3
Dies ist die einfache Lösung und höchstwahrscheinlich das, wonach die Interviewfrage sucht.
Kirk Broadhurst
7
Möglicherweise überprüfen sie sogar, ob Sie nicht unter vorzeitiger Optimierung leiden, es sei denn, sie haben Ihnen auch Laufzeitbeschränkungen gegeben! :-)
Trevor Tippins
16
Lol, obwohl es definitiv schneller ist, das Array zu sortieren und an dem sortierten zu arbeiten. Die Sortierung sollte über eine API erfolgen und ist imho keine vorzeitige Optimierung.
Ziggystar
2
Sollte es nicht while (aktuelles <= Ende) statt while (aktuelles <Ende) sein?
Shail
2
Warum wurde dies als die richtige Antwort akzeptiert? Wenn die Beibehaltung der Ordnung nicht erforderlich ist, ist es nicht besser, nur die Zusammenführungssortierung O (nlogn) zu verwenden und dann die wiederholten Elemente in O (n) zu entfernen ... Gesamtkomplexität - O (nlogn), was viel besser ist als diese Lösung.
Pawan
136

Eine von meiner Freundin vorgeschlagene Lösung ist eine Variation der Zusammenführungssorte. Die einzige Änderung besteht darin, dass während des Zusammenführungsschritts doppelte Werte einfach ignoriert werden. Diese Lösung wäre auch O (n log n). Bei diesem Ansatz werden das Sortieren / Entfernen von Duplikaten miteinander kombiniert. Ich bin mir jedoch nicht sicher, ob das einen Unterschied macht.

Ejel
quelle
8
Toller Vorschlag, aber Sie benötigen einige Buchhaltung, um das Ende jeder Zusammenführungsausgabe zu verfolgen. Ich habe das tatsächlich einmal gemacht, und ja, das Entfernen der Duplikate beim Zusammenführen macht es viel schneller.
Mark Ransom
2
Es ist nicht klar, ob der zusätzliche Speicherplatz von O (N / 2) als die in der Frage verbotene "Hilfsdatenstruktur" gilt. Ich weiß nicht, ob die Einschränkung dazu bestimmt ist, zusätzlichen Speicherplatz von O (1) festzulegen oder nur, dass der Die Antwort sollte nicht von einer großen Implementierung der alten Datenstruktur abhängen. Vielleicht ist eine Standardzusammenführung in Ordnung. Wenn nicht, Top-Tipp: Versuchen Sie nicht, in einem Interview eine direkte Zusammenführungssorte zu schreiben, es sei denn, Sie wissen wirklich , was Sie tun.
Steve Jessop
Großartige Idee. Es ist jedoch erforderlich, dass die verbleibenden Daten die ursprüngliche Reihenfolge beibehalten.
Hardy Feng
4
Ein Papier, das beschreibt, was Ihre Freundin vorgeschlagen hat, folgt: dc-pubs.dbs.uni-leipzig.de/files/…
Mike B
49

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

  1. Nehmen Sie das erste Element des Arrays, dies ist der Sentinel.
  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, für die der Index dem Hash entspricht, an den Anfang des Arrays.
  4. Verschieben Sie alle Elemente, die dem 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 eingefügt werden konnten, der ihrem Hash entspricht. Rückgriff auf diese Elemente.

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

Bearbeiten: In aktuellen Implementierungen von D beträgt hash_t 32 Bit. Alles an diesem Algorithmus geht davon aus, dass es im gesamten 32-Bit-Raum nur sehr wenige, wenn überhaupt, Hash-Kollisionen geben wird. Kollisionen können jedoch häufig im Modulraum auftreten. Diese Annahme gilt jedoch aller Wahrscheinlichkeit nach für jeden Datensatz mit angemessener Größe. Wenn der Schlüssel kleiner oder gleich 32 Bit ist, kann es sich um einen eigenen Hash handeln, was bedeutet, dass eine Kollision im gesamten 32-Bit-Raum unmöglich ist. Wenn es größer ist, können Sie einfach nicht genug davon in den 32-Bit-Speicheradressraum einpassen, damit es ein Problem darstellt. Ich gehe davon aus, dass hash_t in 64-Bit-Implementierungen von D, in denen Datensätze größer sein können, auf 64 Bit erhöht wird. Sollte sich dies jemals als Problem herausstellen, könnte man die Hash-Funktion auf jeder Rekursionsstufe ä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);
}
Dsimcha
quelle
1
Extrem coole, unterschätzte Antwort! Ich mag die Idee, das Element an Position 1 als Sentinel-Wert zu verwenden. Wenn ich ein paar kleine Vorschläge machen könnte, wäre es, Schritt 2 so zu ändern, dass "jedes Element an der Position ist, die seinem Hash- Modulo der Array-Größe entspricht ", und vielleicht klarzustellen, dass die auf den Sentinel zu setzenden Duplikate die sind Elemente, die denselben Wert haben (im Gegensatz zu demselben Hash oder derselben Hash-Modulo-Array-Größe).
j_random_hacker
20

Eine effizientere 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];
}

In dieser Implementierung muss das Array nicht sortiert werden. Auch wenn ein doppeltes Element gefunden wird, müssen nicht alle Elemente danach um eine Position verschoben werden.

Die Ausgabe dieses Codes ist Array [] mit der 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 in Array [1] wird mit Array [0] verglichen. Wenn sie unterschiedlich sind, wird der Wert in Array [NewLength] mit Array [1] geändert und NewLength erhöht. Wenn sie gleich sind, wird NewLength nicht geändert.

Wenn wir also ein Array [1 2 1 3 1] haben, dann

Im ersten Durchgang der 'j'-Schleife wird Array [1] (2) mit Array0 verglichen, dann wird 2 in Array [NewLength] = Array [1] geschrieben, sodass Array [1 2] ist, da NewLength = 2

Im zweiten Durchgang der 'j'-Schleife wird Array [2] (1) mit Array0 und Array1 verglichen. Da Array [2] (1) und Array0 dieselbe Schleife sind, wird hier die Unterbrechung unterbrochen. Das Array ist also [1 2], da NewLength = 2 ist

und so weiter

Byju
quelle
3
Schön. Ich habe einen Verbesserungsvorschlag. Die zweite verschachtelte Schleife kann in (j = 0; j <NewLength; j ++) und zuletzt geändert werden, wenn die Überprüfung in if (j == NewLength) geändert werden kann
Vadakkumpadath
Das war ein großer Vorschlag. Ich habe den Code basierend auf
Ihrem
Scheitern Sie zumindest, wenn wir dieselben Werte im Array {1,1,1,1,1,1} haben. Nutzloser Code.
Yuriy Chernyshov
Was ist die Komplexität davon, ist es nicht auch O (n ^ 2)?
JavaSa
1
So viele positive Stimmen, aber das ist nicht effizient: Es ist O (n ^ 2), wenn es nur wenige Duplikate gibt.
Paul Hankin
19

Wenn Sie nach der überlegenen O-Notation suchen, ist es möglicherweise die beste Route, das Array mit einer O (n log n) -Sortierung zu sortieren und dann eine O (n) -Überquerung durchzuführen. Ohne zu sortieren 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.

Carl
quelle
Jeff Bs Antwort ist nur O (n). Hash-Sets und Hash-Wörterbücher sind die Bienenknie.
ChrisW
3
ChrisW: Hash-Sets / Wörterbücher sind nur O (1), wenn Sie keine Kollisionen annehmen. (Ich sage nicht, dass ich sie nicht für dieses Problem verwenden würde - ich würde es wahrscheinlich tun - es ist nur ein Trugschluss zu behaupten, dass sie wirklich O (1) sind.)
Laurence Gonsalves
2
Da Sie die Größe des Arrays vorher kennen, können Sie O (1) garantieren. Dann können Sie Kollisionen gegen die Menge an zusätzlichem Speicher abwägen, die Sie verwenden.
Vitali
Vielleicht möchten Sie diese Abwertung überdenken - neu veröffentlichte Bedingungen für das Problem machen die Lösung von Jeff B ungültig.
Mark Ransom
3
Möglicherweise möchten Sie die "Durchquerung" näher erläutern, da eine naive Löschmethode für eine große Anzahl von Duplikaten zu O (n ^ 2) führen kann.
Mark Ransom
11

1. Verwenden 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 jedem 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 würde Fälle geben, in denen dies abhängig von der Art der Eingaben ohne Hash-Tabelle sinnvoll wäre. Aber ich habe das nicht wirklich überprüft.

2. Verwenden von O (viel) zusätzlichem Speicherplatz 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 zutreffen:

  • Es ist möglich, Speicher kostengünstig auf Null zu setzen, oder die Größe der Ints ist im Vergleich zu ihrer Anzahl gering
  • Gerne fragen Sie Ihr Betriebssystem nach 256 ^ sizepof (int) Speicher
  • und es wird es für Sie wirklich sehr, sehr effizient zwischenspeichern, wenn es gigantisch ist

Es ist eine schlechte Antwort, aber wenn Sie viele Eingabeelemente haben, aber 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 gering 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 dazu Bibliotheksfunktionen. Effizienz hängt davon ab, welche Sie leicht zur Verfügung haben.

Jack V.
quelle
7

Nun, die grundlegende Implementierung ist recht einfach. Gehen Sie alle Elemente durch, prüfen Sie, ob die verbleibenden Elemente Duplikate enthalten, und verschieben Sie den Rest darüber.

Es ist schrecklich ineffizient und Sie könnten es durch ein Helfer-Array für die Ausgabe oder Sortier- / Binärbäume beschleunigen, aber dies scheint nicht erlaubt zu sein.

Dario
quelle
1
OTOH, der zusätzliche Code, der zum Implementieren eines Sortierbaums erforderlich ist, ist möglicherweise weniger (speicher-) effizient als die einfache Lösung und zur Laufzeit für kleine Arrays (z. B. weniger als 100 Elemente) wahrscheinlich weniger effizient.
TMN
6

Wenn Sie C ++ verwenden dürfen, erhalten Sie die Antwort std::sortdurch einen Aufruf von gefolgt von einem Aufruf an std::unique. Die zeitliche Komplexität beträgt O (N log N) für die Sortierung und O (N) für die eindeutige Durchquerung.

Und wenn C ++ vom Tisch ist, gibt es nichts, was verhindert, dass dieselben Algorithmen in C geschrieben werden.

fbrereto
quelle
"Eine Einschränkung ist, dass der erwartete Algorithmus nicht erfordern sollte, dass das Array zuerst sortiert wird."
sbi
2
Es heißt nicht, dass Sie das Array nicht sortieren können, sobald Sie es erhalten haben ... Ohne O (N) ist die externe Speichersortierung die einzige Möglichkeit, dies in O (N log N) oder besser zu tun.
Greg Rogers
Für das Problem sollten keine Standard-Bibliotheks-Utils verwendet werden. In Bezug auf das Sortieren bin ich mir jedoch nicht mehr sicher, ob es in Ordnung ist oder nicht, je mehr ich darüber nachdenke.
Ejel
1
Ich denke, Antworten, die sich auf C ++ - und C ++ - Standardfunktionen beziehen, sind nützlich, auch wenn sie die ursprüngliche Frage nicht beantworten, da sie eine rundere Antwort für Personen bieten, die diese Frage später finden.
Douglas Leeder
6

Sie könnten dies in einer einzigen Durchquerung tun, wenn Sie bereit sind, die Erinnerung zu opfern. Sie können einfach abrechnen, ob Sie eine Ganzzahl in einem Hash / assoziativen Array gesehen haben oder nicht. Wenn Sie bereits eine Zahl gesehen haben, entfernen Sie sie, während Sie fortfahren, oder verschieben Sie noch besser Zahlen, die Sie nicht gesehen haben, in ein neues Array, um eine Verschiebung des ursprünglichen Arrays zu vermeiden.

In Perl:

foreach $i (@myary) {
    if(!defined $seen{$i}) {
        $seen{$i} = 1;
        push @newary, $i;
    }
}
Jeff B.
quelle
Es ist nicht klar, ob die Antwort im ursprünglichen Array sein muss.
Douglas Leeder
Um dies zu tun, ohne dass ein neues Array erforderlich ist, können Sie das Duplikat einfach durch ein Element ersetzen, das am Ende des Arrays angezeigt wird, und die aktuelle Schleife wiederholen, da das Problem nicht angibt, dass die Reihenfolge von Bedeutung ist. Dies erfordert einige zusätzliche Grenzüberprüfungen, ist jedoch sehr machbar.
Jeff B
6
Dies war eine gute Idee, bis die Frage bearbeitet wurde. Ihre Hashtable-Idee verstößt offenbar gegen die Regeln.
WCWedin
14
Ich verstehe nicht, warum diese Antwort am meisten gewählt wird. Es ist in Perl geschrieben und verwendet wichtige Funktionen, die in C nicht verfügbar sind, wie die Frage stellt.
LiraNuna
5
Die Frage nach C-Code, nicht nach Perl. Mit Perl erhalten Sie Hashtabellen und "Push" kostenlos. Wenn ich es in Scala machen könnte, würden Sie einfach input.removeDuplicates aufrufen, aber ich bezweifle, dass dies für die Interviewer akzeptabel gewesen wäre :)
Peter Recore
5

Der Rückgabewert der Funktion sollte die Anzahl der eindeutigen Elemente sein und alle werden an der Vorderseite des Arrays gespeichert. Ohne diese zusätzlichen Informationen wissen Sie nicht einmal, ob es Duplikate gab.

Jede Iteration der äußeren Schleife verarbeitet ein Element des Arrays. Wenn es eindeutig ist, bleibt es im vorderen Bereich des Arrays und wenn es ein Duplikat ist, wird es vom letzten unverarbeiteten Element im Array überschrieben. Diese Lösung läuft in O (n ^ 2) Zeit.

#include <stdio.h>
#include <stdlib.h>

size_t rmdup(int *arr, size_t len)
{
  size_t prev = 0;
  size_t curr = 1;
  size_t last = len - 1;
  while (curr <= last) {
    for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
    if (prev == curr) {
      ++curr;
    } else {
      arr[curr] = arr[last];
      --last;
    }
  }
  return curr;
}

void print_array(int *arr, size_t len)
{
  printf("{");
  size_t curr = 0;
  for (curr = 0; curr < len; ++curr) {
    if (curr > 0) printf(", ");
    printf("%d", arr[curr]);
  }
  printf("}");
}

int main()
{
  int arr[] = {4, 8, 4, 1, 1, 2, 9};
  printf("Before: ");
  size_t len = sizeof (arr) / sizeof (arr[0]);
  print_array(arr, len);
  len = rmdup(arr, len);
  printf("\nAfter: ");
  print_array(arr, len);
  printf("\n");
  return 0;
}
dsh
quelle
4

Hier ist eine Java-Version.

int[] removeDuplicate(int[] input){

        int arrayLen = input.length;
        for(int i=0;i<arrayLen;i++){
            for(int j = i+1; j< arrayLen ; j++){
                if(((input[i]^input[j]) == 0)){
                    input[j] = 0;
                }
                if((input[j]==0) && j<arrayLen-1){
                        input[j] = input[j+1];
                        input[j+1] = 0;
                    }               
            }
        }       
        return input;       
    }
Naren
quelle
Schlägt zumindest bei den nächsten Eingaben fehl: {1,1,1,1,1,1,1} {0,0,0,0,0,1,1,1,1,1,1}
Yuriy Chernyshov
3

Hier ist meine Lösung.

///// find duplicates in an array and remove them

void unique(int* input, int n)
{
     merge_sort(input, 0, n) ;

     int prev = 0  ;

     for(int i = 1 ; i < n ; i++)
     {
          if(input[i] != input[prev])
               if(prev < i-1)
                   input[prev++] = input[i] ;                         
     }
}
kiriloff
quelle
2

Ein Array sollte natürlich von rechts nach links "durchlaufen" werden, um unnötiges Kopieren von Werten hin und her zu vermeiden.

Wenn Sie über unbegrenzten Speicher verfügen, können Sie sizeof(type-of-element-in-array) / 8Bytes ein Bitarray zuweisen , damit jedes Bit anzeigt, ob Sie bereits auf einen entsprechenden Wert gestoßen sind oder nicht.

Wenn Sie dies nicht tun, kann ich mir nichts Besseres vorstellen, als ein Array zu durchlaufen und jeden Wert mit den darauf folgenden Werten zu vergleichen. Wenn dann ein Duplikat gefunden wird, entfernen Sie diese Werte vollständig. Dies ist irgendwo in der Nähe von O (n ^ 2) (oder O ((n ^ 2-n) / 2) ).

IBM hat einen Artikel zu einem ziemlich engen Thema.

Anton Gogolev
quelle
In der Tat würde ein O (n) -Pass zum Finden des größten Elements die Gesamtkosten für O () nicht erhöhen.
Douglas Leeder
2

Mal schauen:

  • O (N) Pass, um die Min / Max-Zuordnung zu finden
  • Bit-Array für gefunden
  • O (N) Pass-Swap-Duplikate zum Ende.
Douglas Leeder
quelle
Da es sich nur um Ganzzahlen handelt, können Sie der Einfachheit halber davon ausgehen, dass 32 Bit und nicht nach Min / Max suchen: 2 ^ 32 Bit sind "nur" 512 MB. Das Finden der Grenzen ist also nur eine Speicherauslastung und eine O (1) -Zeitoptimierung (Zugegeben, eine kräftige Optimierung im Fall des angegebenen Beispiels). Und wenn es sich um 64-Bit handelt, ist dies irrelevant, da Sie nicht wissen, dass Min und Max nicht weiter voneinander entfernt sind als die Anzahl der verfügbaren Speicherbits.
Steve Jessop
Abgesehen von der Theorie, würde die Zuweisung von 512 MB nicht mehr Zeit in Anspruch nehmen als das Finden des Min / Max?
LiraNuna
Hängt davon ab, wie viele Daten vorhanden sind und wie hoch die Min / Max sind. Wenn Sie mehr als 512 MB Eingang sehen, ist es möglicherweise schneller, diesen zusätzlichen O (N) -Pass zu vermeiden. Wenn Sie sich so viel Input ansehen, ist es natürlich weniger wahrscheinlich, dass Sie 512 MB übrig haben. In Fällen, in denen die Min / Max nahe bei 0 / INT_MAX liegen, hilft die Optimierung ebenfalls nicht. Ich sage nur, dass der erste Schritt zwar offensichtlich für kleine Zahlen hilft, aber nicht vermeiden kann, dass dieser Algorithmus im schlimmsten Fall UINT_MAX-Bits verwendet. Sie müssen also diese Einschränkung einplanen.
Steve Jessop
Sie haben vielleicht Recht - in jedem Fall bedeutet die Klärung der Frage, dass die Verwendung eines Bit-Arrays nicht möglich ist. Ich werde diese Antwort hinterlassen, falls jemand später ohne Einschränkungen vorbeikommt und alle möglichen Antworten anzeigen möchte.
Douglas Leeder
2

Dies kann in einem Durchgang mit einem O (N log N) -Algorithmus und ohne zusätzlichen Speicher erfolgen.

Fahren Sie vom Element a[1]zum fort a[N]. Auf jeder Stufe i, alle Elemente auf der linken Seite a[i]umfassen einen sortierten Haufen von Elementen a[0]durch a[j]. Währenddessen verfolgt ein zweiter Index j, anfangs 0, die Größe des Heaps.

Untersuchen a[i]und in den Haufen legen, die nun Elemente nimmt a[0]zu a[j+1]. Wenn beim Einfügen des Elements ein doppeltes Element a[k]mit demselben Wert gefunden wird, fügen Sie es nicht a[i]in den Heap ein (dh verwerfen Sie es). Andernfalls fügen Sie es in den Heap ein, der jetzt um ein Element wächst und jetzt a[0]to a[j+1]und inkrementiert j.

Fahren Sie auf diese Weise zu inkrementieren , ibis alle der Array - Elemente untersucht worden sind und in den Heap eingefügt, die Besatzungs endet a[0]an a[j]. jist der Index des letzten Elements des Heaps, und der Heap enthält nur eindeutige Elementwerte.

int algorithm(int[] a, int n)
{
    int   i, j;  

    for (j = 0, i = 1;  i < n;  i++)
    {
        // Insert a[i] into the heap a[0...j]
        if (heapInsert(a, j, a[i]))
            j++;
    }
    return j;
}  

bool heapInsert(a[], int n, int val)
{
    // Insert val into heap a[0...n]
    ...code omitted for brevity...
    if (duplicate element a[k] == val)
        return false;
    a[k] = val;
    return true;
}

Im Beispiel ist dies nicht genau das, wonach gefragt wurde, da das resultierende Array die ursprüngliche Elementreihenfolge beibehält. Wenn diese Anforderung jedoch gelockert wird, sollte der obige Algorithmus den Trick ausführen.

David R Tribble
quelle
1

In Java würde ich es so lösen. Ich weiß nicht, wie ich das in C schreiben soll.

   int length = array.length;
   for (int i = 0; i < length; i++) 
   {
      for (int j = i + 1; j < length; j++) 
      {
         if (array[i] == array[j]) 
         {
            int k, j;
            for (k = j + 1, l = j; k < length; k++, l++) 
            {
               if (array[k] != array[i]) 
               {
                  array[l] = array[k];
               }
               else
               {
                  l--;
               }
            }
            length = l;
         }
      }
   }
Dominik
quelle
Wenn Sie die gefundenen Duplikate mit dem Wert am Ende des Arrays überschreiben, können Sie die Verschiebung des gesamten Arrays in Ihrer inneren for () - Schleife vermeiden. Das bringt dich von O (n ^ 3) zu O (n ^ 2). Meine C-Implementierung schwebt hier irgendwo herum ...
mocj
Ich dachte, das Schalten war Teil der Anforderung, aber Sie haben natürlich Recht.
Dominik
1
@mocj: Ich mag deine Lösung, sieht sehr elegant aus. Aber ich denke, es funktioniert nicht, wenn die letzten beiden Elemente gleich sind, weil Sie aufhören, vor dem letzten auf Gleichheit zu prüfen. (Kommentar hier, weil ich den Ruf zu sehen habe, um ihn irgendwo anders zu kommentieren :()
Dominik
Sie haben Recht, außer dass das ursprüngliche Problem besagt, dass die Werte am Ende des Arrays vernachlässigbar sind. Da Sie die Länge des geänderten Arrays nicht zurückgeben, ist die Unterscheidung zwischen dem letzten und dem vorletzten Wert unwichtig, wenn die beiden Werte gleich sind. Wo interpretiert der Aufrufer das Ende des zurückgegebenen Arrays als
mocj
1

Wie wäre es mit folgendem?

int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
    for(y=0;y<count;y++)
    {
        if(*(temp+y)==*(array+x))
        {
            break;
        }
    }
    if(y==count)
    {
        *(temp+count) = *(array+x);
        count++;
    }
}
memcpy(array, temp, sizeof(int)*len);

Ich versuche, ein temporäres Array zu deklarieren und die Elemente darin zu platzieren, bevor ich alles zurück in das ursprüngliche Array kopiere.

Charith
quelle
1

Nach Überprüfung des Problems ist hier mein Delphi-Weg, der helfen kann

var
A: Array of Integer;
I,J,C,K, P: Integer;
begin
C:=10;
SetLength(A,10);
A[0]:=1; A[1]:=4; A[2]:=2; A[3]:=6; A[4]:=3; A[5]:=4;
A[6]:=3; A[7]:=4; A[8]:=2; A[9]:=5;

for I := 0 to C-1 do
begin
  for J := I+1 to C-1 do
    if A[I]=A[J] then
    begin
      for K := C-1 Downto J do
        if A[J]<>A[k] then
        begin
          P:=A[K];
          A[K]:=0;
          A[J]:=P;
          C:=K;
          break;
        end
        else
        begin
          A[K]:=0;
          C:=K;
        end;
    end;
end;

//tructate array
setlength(A,C);
end;
RichardLi
quelle
1

Das folgende Beispiel sollte Ihr Problem lösen:

def check_dump(x):
   if not x in t:
      t.append(x)
      return True

t=[]

output = filter(check_dump, input)

print(output)
True
yupbank
quelle
1
import java.util.ArrayList;


public class C {

    public static void main(String[] args) {

        int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};

        ArrayList<Integer> arr1 = new ArrayList<Integer>();

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

            if(arr[i] == arr[i+1]){
                arr[i] = 99999;
            }
        }

        for(int i=0;i<arr.length;i++){
            if(arr[i] != 99999){

                arr1.add(arr[i]);
            }
        }

        System.out.println(arr1);
}
    }
user1423581
quelle
arr [i + 1] sollte ArrayIndexOutOfBoundsException für das letzte Element auslösen?
Sathesh
@Sathesh Nein. Wegen "<arr.length-1"
GabrielBB
1

Dies ist die naive (N * (N-1) / 2) Lösung. Es benötigt ständig zusätzlichen Platz und behält die ursprüngliche Reihenfolge bei. Es ähnelt der Lösung von @Byju, verwendet jedoch keine if(){}Blöcke. Außerdem wird vermieden, dass ein Element auf sich selbst kopiert wird.

#include <stdio.h>
#include <stdlib.h>

int numbers[] = {4, 8, 4, 1, 1, 2, 9};
#define COUNT (sizeof numbers / sizeof numbers[0])

size_t undup_it(int array[], size_t len)
{
size_t src,dst;

  /* an array of size=1 cannot contain duplicate values */
if (len <2) return len; 
  /* an array of size>1 will cannot at least one unique value */
for (src=dst=1; src < len; src++) {
        size_t cur;
        for (cur=0; cur < dst; cur++ ) {
                if (array[cur] == array[src]) break;
                }
        if (cur != dst) continue; /* found a duplicate */

                /* array[src] must be new: add it to the list of non-duplicates */
        if (dst < src) array[dst] = array[src]; /* avoid copy-to-self */
        dst++;
        }
return dst; /* number of valid alements in new array */
}

void print_it(int array[], size_t len)
{
size_t idx;

for (idx=0; idx < len; idx++)  {
        printf("%c %d", (idx) ? ',' :'{' , array[idx] );
        }
printf("}\n" );
}

int main(void) {    
    size_t cnt = COUNT;

    printf("Before undup:" );    
    print_it(numbers, cnt);    

    cnt = undup_it(numbers,cnt);

    printf("After undup:" );    
    print_it(numbers, cnt);

    return 0;
}
Wildplasser
quelle
0

Dies kann in einem einzigen Durchgang erfolgen, in O (N) -Zeit in der Anzahl der Ganzzahlen in der Eingabeliste und O (N) -Speicher in der Anzahl der eindeutigen Ganzzahlen.

Gehen Sie die Liste von vorne nach hinten durch, wobei zwei Zeiger "dst" und "src" auf das erste Element initialisiert werden. Beginnen Sie mit einer leeren Hash-Tabelle mit "Ganzzahlen gesehen". Wenn die Ganzzahl bei src nicht im Hash vorhanden ist, schreiben Sie sie in den Slot bei dst und erhöhen Sie dst. Fügen Sie die Ganzzahl bei src zum Hash hinzu und erhöhen Sie dann src. Wiederholen, bis src das Ende der Eingabeliste passiert.

Andy Ross
quelle
2
Bei der Änderung der ursprünglichen Frage sind Hash-Tabellen nicht zulässig. Ihr Zwei-Zeiger-Ansatz ist jedoch eine gute Möglichkeit, die Ausgabe zu komprimieren, sobald Sie die Duplikate identifiziert haben.
Mark Ransom
0

Fügen Sie alle Elemente in ein binary tree the disregards duplicates- ein O(nlog(n)). Extrahieren Sie dann alle wieder in das Array, indem Sie eine Durchquerung durchführen - O(n). Ich gehe davon aus, dass Sie keine Auftragserhaltung benötigen.

Ashwin
quelle
0

Verwenden Sie zum Hashing den Bloom-Filter. Dadurch wird der Speicheraufwand erheblich reduziert.

Gaurav Gupta
quelle
Möchten Sie eine Referenz ausarbeiten oder bereitstellen?
dldnh
0

In JAVA,

    Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};

    String value ="";

    for(Integer i:arrayInteger)
    {
        if(!value.contains(Integer.toString(i))){
            value +=Integer.toString(i)+",";
        }

    }

    String[] arraySplitToString = value.split(",");
    Integer[] arrayIntResult = new Integer[arraySplitToString.length];
    for(int i = 0 ; i < arraySplitToString.length ; i++){
        arrayIntResult[i] = Integer.parseInt(arraySplitToString[i]);
    }

Ausgabe: {1, 2, 3, 4, 6, 7, 8, 9, 10}

hoffe das wird helfen

PRABHU SEKAR
quelle
1
Testen Sie dies mit der EingabearrayInteger = {100,10,1};
Blastfurnace
0

Zunächst sollten Sie ein Array erstellen, check[n]wobei n die Anzahl der Elemente des Arrays ist, die Sie duplikationsfrei machen möchten, und den Wert jedes Elements (des Prüfarrays) auf 1 setzen. Verwenden Sie eine for-Schleife, um das Array mit dem zu durchlaufen Duplikate, sagen wir, sein Name ist arr, und schreiben Sie dies in die for-Schleife:

{
    if (check[arr[i]] != 1) {
        arr[i] = 0;
    }
    else {
        check[arr[i]] = 0;
    }
}

Damit setzen Sie jedes Duplikat auf Null. Sie müssen also nur noch das arrArray durchlaufen und alles drucken, was nicht gleich Null ist. Die Reihenfolge bleibt bestehen und es dauert eine lineare Zeit (3 * n).

Benutzer3727788
quelle
Die Frage erlaubt keine zusätzliche Datenstruktur.
Ejel
0

Schreiben Sie bei einem Array von n Elementen einen Algorithmus, um alle Duplikate in der Zeit O (nlogn) aus dem Array zu entfernen.

Algorithm delete_duplicates (a[1....n])
//Remove duplicates from the given array 
//input parameters :a[1:n], an array of n elements.

{

temp[1:n]; //an array of n elements. 

temp[i]=a[i];for i=1 to n

 temp[i].value=a[i]

temp[i].key=i

 //based on 'value' sort the array temp.

//based on 'value' delete duplicate elements from temp.

//based on 'key' sort the array temp.//construct an array p using temp.

 p[i]=temp[i]value

  return p.

In anderen Elementen wird im Ausgabearray mit dem 'Schlüssel' gepflegt. Angenommen, der Schlüssel hat die Länge O (n), die Zeit, die zum Sortieren des Schlüssels und des Werts benötigt wird, ist O (nlogn). Die zum Löschen aller Duplikate aus dem Array benötigte Zeit beträgt also O (nlogn).

Sharief Muzammil
quelle
Woraus haben Sie trotz aller kühnen Glyphen gemacht helper data structure (e.g. hashtable) should not be used?
Graubart
Nicht unbedingt erforderlich. Ich habe diese nur zum Zwecke des Verständnisses hervorgehoben.
Sharief Muzammil
0

Dies ist, was ich habe, obwohl es die Reihenfolge, die wir in aufsteigender oder absteigender Reihenfolge sortieren können, um es zu reparieren, falsch platziert.

#include <stdio.h>
int main(void){
int x,n,myvar=0;
printf("Enter a number: \t");
scanf("%d",&n);
int arr[n],changedarr[n];

for(x=0;x<n;x++){
    printf("Enter a number for array[%d]: ",x);
    scanf("%d",&arr[x]);
}
printf("\nOriginal Number in an array\n");
for(x=0;x<n;x++){
    printf("%d\t",arr[x]);
}

int i=0,j=0;
// printf("i\tj\tarr\tchanged\n");

for (int i = 0; i < n; i++)
{
    // printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
    for (int j = 0; j <n; j++)
    {   
        if (i==j)
        {
            continue;

        }
        else if(arr[i]==arr[j]){
            changedarr[j]=0;

        }
        else{
            changedarr[i]=arr[i];

        }
    // printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
    }
    myvar+=1;
}
// printf("\n\nmyvar=%d\n",myvar);
int count=0;
printf("\nThe unique items:\n");
for (int i = 0; i < myvar; i++)
{
        if(changedarr[i]!=0){
            count+=1;
            printf("%d\t",changedarr[i]);   
        }
}
    printf("\n");
}
ashim888
quelle
-1

Es wäre cool, wenn Sie eine gute DataStructure hätten, die schnell erkennen könnte, ob sie eine Ganzzahl enthält. Vielleicht ein Baum.

DataStructure elementsSeen = new DataStructure();
int elementsRemoved = 0;
for(int i=0;i<array.Length;i++){
  if(elementsSeen.Contains(array[i])
    elementsRemoved++;
  else
    array[i-elementsRemoved] = array[i];
}
array.Length = array.Length - elementsRemoved;
Mike Blandford
quelle