wake-up-neo.com

Algorithmus: effiziente Methode zum Entfernen doppelter Ganzzahlen aus einem Array

Ich habe dieses Problem aus einem Interview mit Microsoft erhalten.

Angenommen, ein Array von Zufallszahlen ist schreibe einen Algorithmus in C, der .__ entfernt. doppelte Nummern und geben die eindeutigen Nummern im Original zurück Array.

ZB Eingabe: {4, 8, 4, 1, 1, 2, 9} Ausgabe: {4, 8, 1, 2, 9, ?, ?}

Ein Nachteil ist, dass der erwartete Algorithmus das Array nicht zuerst sortieren muss. Und wenn ein Element entfernt wurde, müssen auch die folgenden Elemente nach vorne verschoben werden. In jedem Fall ist der Wert der Elemente am Ende des Arrays, an dem Elemente nach vorne verschoben wurden, vernachlässigbar. 

Update: Das Ergebnis muss im ursprünglichen Array zurückgegeben werden. Die Helper-Datenstruktur (z. B. Hashtabelle) sollte nicht verwendet werden. Ich denke jedoch, dass die Auftragserhaltung nicht notwendig ist.

Update2: Für diejenigen, die sich fragen, warum diese unpraktischen Zwänge, war dies eine Interviewfrage, und alle diese Zwänge werden während des Denkprozesses besprochen, um zu sehen, wie ich verschiedene Ideen habe.

84
ejel

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.

18
mocj

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

132
ejel

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

  1. Nehmen Sie das erste Element des Arrays, dies ist das 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 erkannt. Setze sie gleich Sentinel.
  3. Verschieben Sie alle Elemente, für die der Index gleich dem Hash ist, an den Anfang des Arrays.
  4. Verschieben Sie alle Elemente mit Ausnahme des ersten Elements des Arrays, die dem Sentinel entsprechen, an das Ende des Arrays.
  5. Was zwischen den ordnungsgemäß gehashten Elementen und den doppelten Elementen übrig bleibt, sind die Elemente, die aufgrund einer Kollision nicht in den Index eingefügt werden könnten, der ihrem Hash entspricht. Bitte wenden Sie sich an diese Elemente.

Es kann gezeigt werden, dass O(N) kein pathologisches Szenario im Hashing enthält: Selbst wenn keine Duplikate vorhanden sind, werden bei jeder Rekursion etwa 2/3 der Elemente entfernt. Jede Rekursionsebene ist O(n), wobei kleines n die Anzahl der verbleibenden Elemente ist. Das einzige Problem ist, dass es in der Praxis langsamer ist als eine schnelle Sortierung, wenn es wenige Duplikate gibt, d. H. Viele Kollisionen. Wenn es jedoch sehr viele Duplikate gibt, ist es erstaunlich schnell.

Edit: In aktuellen Implementierungen von D ist hash_t 32 Bit. Alles an diesem Algorithmus geht davon aus, dass es nur sehr wenige Hash-Kollisionen im gesamten 32-Bit-Bereich geben wird. Im Modulraum können jedoch häufig Kollisionen auftreten. Diese Annahme wird jedoch aller Wahrscheinlichkeit nach für jeden Datensatz von angemessener Größe 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 gesamten 32-Bit-Bereich unmöglich ist. Wenn es größer ist, können Sie einfach nicht genug davon in den 32-Bit-Speicheradressraum einfügen, um ein Problem darzustellen. Ich gehe davon aus, dass hash_t in 64-Bit-Implementierungen von D auf 64 Bit erhöht wird, wobei Datensätze größer sein können. Wenn sich dies jemals als Problem erwies, 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);
}
45
dsimcha

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

Bei dieser Implementierung muss das Array nicht sortiert werden. Auch wenn ein Element doppelt vorhanden ist, müssen nicht alle Elemente um eine Position verschoben werden.

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

Hier beginnen wir mit dem zweiten Element in array und vergleichen es mit allen Elementen in array bis zu diesem Array .. _. Wir halten eine zusätzliche Indexvariable 'NewLength' zum Ändern des Eingabearrays . NewLength-Variable wird initialisiert bis 0.

Das 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 .__

In First pass of 'j' Loop wird Array [1] (2) mit Array0 verglichen, dann wird 2 in Array [NewLength] = Array [1] Geschrieben. Das Array ist also seit NewLength [1 2] = 2

Im zweiten Durchlauf der "j" -Schleife wird Array [2] (1) mit Array0 und Array1 verglichen. Da hier Array [2] (1) und Array0 die gleiche Schleife sind, bricht hier . Array ist also [1 2], da NewLength = 2 ist

und so weiter

20
Byju

Wenn Sie nach der überragenden O-Notation suchen, ist das Sortieren des Arrays mit einer O (n log n) -Sortierung die beste Route, wenn Sie eine O(n) - Durchquerung durchführen. Ohne zu sortieren, betrachten Sie O (n ^ 2).

Edit: Wenn Sie nur ganze Zahlen machen, können Sie auch radix sortieren, um O (n) zu erhalten.

19
carl

1. Mit O(1) zusätzlichen Speicherplatz in der Zeit O (n log n)

Dies ist zum Beispiel möglich:

  • zuerst führen Sie eine In-Place-O (n log n) -Sortierung durch
  • gehen Sie dann die Liste einmal durch und schreiben Sie die erste Instanz an den Anfang der Liste

Ich glaube, dass Ejels Partner richtig ist, dass der beste Weg, dies zu tun, eine direkte Zusammenführungssortierung mit einem vereinfachten Zusammenführungsschritt wäre. Schreiben einer neuen Bibliotheksfunktion, um dies so effizient wie möglich zu machen, ohne die Möglichkeiten zur Verbesserung der Eingaben zu haben. In manchen Fällen kann es sinnvoll sein, dies ohne Hash-Tabelle zu tun, abhängig von den Eingaben. Aber ich habe das nicht wirklich geprüft.

2. Mit O(lots) zusätzlichen Speicherplatz in O(n) Zeit

  • deklarieren Sie ein Null-Array, das groß genug ist, um alle ganzen Zahlen zu speichern
  • einmal durch das Array gehen
  • setzen Sie das entsprechende Array-Element für jede ganze Zahl auf 1.
  • Wenn es bereits 1 war, überspringen Sie diese Ganzzahl.

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

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

Das ist eine schlechte Antwort, aber wenn Sie LOTS von Eingangselementen haben, aber dies sind alle 8-Bit-Ganzzahlen (oder vielleicht sogar 16-Bit-Integer), könnte dies der beste Weg sein.

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

Wie # 2, aber eine Hashtabelle verwenden.

4. Der klare Weg

Wenn die Anzahl der Elemente gering ist, ist das Schreiben eines geeigneten Algorithmus nicht hilfreich, wenn anderer Code schneller geschrieben und gelesen werden kann.

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 Platz, O (n ^ 2) Zeit.

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

10
Jack V.

Nun, die grundlegende Implementierung ist recht einfach. Gehen Sie alle Elemente durch, prüfen Sie, ob die restlichen Elemente doppelt vorhanden sind, 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.

7
Dario

Sie können dies in einem einzigen Durchlauf tun, wenn Sie das Gedächtnis opfern möchten. Sie können einfach nachzählen, ob Sie in einem Hash/Assoziativ-Array eine ganze Zahl gesehen haben oder nicht. Wenn Sie bereits eine Zahl gesehen haben, entfernen Sie sie, oder verschieben Sie Zahlen, die Sie noch nicht gesehen haben, in ein neues Array, um Verschiebungen im ursprünglichen Array zu vermeiden.

In Perl:

foreach $i (@myary) {
    if(!defined $seen{$i}) {
        $seen{$i} = 1;
        Push @newary, $i;
    }
}
6
Jeff B

Der Rückgabewert der Funktion sollte die Anzahl der eindeutigen Elemente sein, die alle am Anfang des Arrays gespeichert sind. Ohne diese zusätzlichen Informationen wissen Sie nicht einmal, ob Duplikate vorhanden waren.

Jede Iteration der äußeren Schleife verarbeitet ein Element des Arrays. Wenn es eindeutig ist, bleibt es im vorderen Teil des Arrays. Wenn es sich um ein Duplikat handelt, wird es vom letzten nicht verarbeiteten 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;
}
5
dsh

Wenn Sie C++ verwenden dürfen, erhalten Sie die Antwort, wenn Sie std::sort gefolgt von einem Aufruf von std::unique aufrufen. 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++ nicht in der Tabelle ist, gibt es nichts, was diese Algorithmen davon abhält, in C geschrieben zu werden.

5
fbrereto

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;       
    }
4
Naren

Ein Array sollte offensichtlich von rechts nach links "durchlaufen" werden, um das unnötige Kopieren von Werten zu vermeiden.

Wenn Sie über unbegrenzten Speicher verfügen, können Sie ein Bitfeld für sizeof(type-of-element-in-array) / 8 Bytes zuweisen, damit jedes Bit anzeigt, ob Sie bereits einen entsprechenden Wert gefunden haben oder nicht.

Wenn dies nicht der Fall ist, kann ich mir nichts Besseres vorstellen, als ein Array zu durchqueren und jeden Wert mit den folgenden Werten zu vergleichen. Wenn Du ein Duplikat gefunden hast, entferne diese Werte dann ganz. Dies ist irgendwo in der Nähe von O (n ^ 2) (oder O ((n ^ 2-n)/2)).

IBM hat ein Artikel zu einem nahen Thema.

2
Anton Gogolev

Mal schauen:

  • O (N) durchlaufen, um Min/Max-Zuordnung zu finden
  • bit-Array für gefunden 
  • O (N) durchlaufen den Austausch von Duplikaten bis zum Ende.
2
Douglas Leeder

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] ;                         
     }
}
2
octoback
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);
}
    }
1
Ankit Jain

Dies ist die naive (N * (N-1)/2) -Lösung. Es verwendet ständig zusätzlichen Speicherplatz und behält die ursprüngliche Reihenfolge bei. Sie ähnelt der Lösung von @Byju, verwendet jedoch keine if(){}-Blöcke. Es vermeidet auch, ein Element auf sich selbst zu kopieren.

#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;
}
1
wildplasser

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;
         }
      }
   }
1
Dominik

Nach der Überprüfung des Problems, hier ist meine Delphi-Methode, die 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;
1
RichardLi

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

Fahren Sie vom Element a[1] bis a[N] fort. In jeder Stufe i umfassen alle Elemente links von a[i] einen sortierten Haufen von Elementen a[0] bis a[j]. Ein zweiter Index j, anfangs 0, verfolgt die Größe des Heapspeichers.

a[i] untersuchen und in den Heap einfügen, der jetzt die Elemente a[0] bis a[j+1] einnimmt. Wenn das Element eingefügt wird und ein Duplikatelement a[k] mit demselben Wert angetroffen wird, fügen Sie a[i] nicht in den Heap ein (d. H. Verwerfen Sie es). Andernfalls fügen Sie es in den Heap ein, der jetzt um ein Element wächst und nun aus a[0] bis a[j+1] besteht und j inkrementiert.

Fahren Sie auf diese Weise fort und erhöhen Sie i, bis alle Array-Elemente untersucht und in den Heap eingefügt wurden, wodurch a[0] bis a[j] belegt wird. j ist der Index des letzten Elements des Heapspeichers. Der Heapspeicher 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;
}

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

1
David R Tribble

Wie wäre es mit dem Folgenden?

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.

1
Charith

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
1
yupbank

Dies kann in einem einzigen Durchgang durchgeführt werden, in O(N) - Zeit in der Anzahl von Ganzzahlen in der Eingabe Liste und O(N) in der Anzahl von 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 .__ von "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 Sie diesen Vorgang, bis src das Ende der Eingabeliste passiert.

0
Andy Ross

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

0
PRABHU SEKAR

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

0
gaurav gupta

Erstellen Sie eine BinarySearchTree , die Komplexität O(n) hat.

0
cpp

Schreibe für einen Array von n Elementen einen Algorithmus, um alle Duplikate rechtzeitig aus dem Array zu entfernen O(nlogn)

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 das Ausgabearray mit 'key' verwaltet. Angenommen, der Schlüssel hat die Länge O (n), die Zeit zum Durchführen der Sortierung nach Schlüssel und Wert ist O (nlogn). Die Zeit, die zum Löschen aller Duplikate aus dem Array benötigt wird, ist also O (nlogn).

0

das ist, was ich habe, obwohl es die Reihenfolge verfälscht, die wir sortieren können, um es zu ordnen.

#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");
}
0
ashim888

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

0
Ashwin

Erstellen Sie zunächst ein Array check[n], wobei n die Anzahl der Elemente des Arrays ist, die Sie duplizieren möchten, und legen Sie den Wert jedes Elements (des Check-Arrays) auf 1 fest. Verwenden Sie eine for-Schleife, um das Array mit zu durchlaufen die Duplikate, sagen wir, ihr Name ist arr, und schreiben Sie in der for-Schleife folgendes:

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

Damit setzen Sie jedes Duplikat gleich Null. Das einzige, was zu tun bleibt, ist, das arr-Array zu durchlaufen und alles auszudrucken, was nicht gleich Null ist. Die Reihenfolge bleibt und es dauert eine lineare Zeit (3 * n).

0
Grabenfly