Array entfernt doppelte Elemente

Ich habe ein unsortiertes Array, was ist die beste Methode, um alle Duplikate eines Elements zu entfernen, wenn vorhanden?

z.B:

a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3] 

Nach dieser Operation sollte das Array wie folgt aussehen

  a[1,5,2,6,8,9,10,3,4,11] 

Überprüfen Sie jedes Element gegen jedes andere Element

Die naive Lösung besteht darin, jedes Element gegen jedes andere Element zu prüfen. Dies ist verschwenderisch und ergibt eine O (n 2 ) -Lösung, auch wenn Sie nur “vorwärts” gehen.

Sortieren und entfernen Sie die Duplikate

Eine bessere Lösung ist, das Array zu sortieren und dann jedes Element auf das nächste zu prüfen, um Duplikate zu finden. Wählen Sie eine effiziente Sortierung und das ist O (n log n).

Der Nachteil bei der sortbasierten Lösung ist, dass die Reihenfolge nicht eingehalten wird. Ein zusätzlicher Schritt kann jedoch dafür sorgen. Setzen Sie alle Einträge (im eindeutigen sortierten Array) in eine Hashtabelle, die O (1) -Zugriff hat. Dann iteriere über das ursprüngliche Array. Überprüfen Sie für jedes Element, ob es sich in der Hash-Tabelle befindet. Wenn dies der Fall ist, fügen Sie es dem Ergebnis hinzu und löschen Sie es aus der Hash-Tabelle. Sie erhalten am Ende ein resultierendes Array, das die Reihenfolge des Originals hat, wobei jedes Element an derselben Position wie sein erstes Auftreten ist.

Lineare Arten von ganzen Zahlen

Wenn es sich um Ganzzahlen mit festem Bereich handelt, können Sie mit einer Radix-Sortierung noch besser arbeiten. Wenn Sie annehmen, dass die Zahlen zum Beispiel alle im Bereich von 0 bis 1.000.000 liegen, können Sie einen Bitvektor von 1.000.001 zuweisen. Für jedes Element im ursprünglichen Array setzen Sie das entsprechende Bit basierend auf seinem Wert (z. B. ergibt ein Wert von 13 das Setzen des 14. Bits). Durchqueren Sie dann das ursprüngliche Array und prüfen Sie, ob es sich im Bitvektor befindet. Wenn dies der Fall ist, fügen Sie es zum Ergebnisarray hinzu und löschen Sie dieses Bit vom Bitvektor. Dies ist O (n) und handelt Raum für Zeit.

Hash-Tabellenlösung

Was uns zu der besten Lösung führt: Die Sorte ist eigentlich eine Ablenkung, obwohl sie nützlich ist. Erstellen Sie eine Hashtabelle mit O (1) -Zugriff. Durchsuche die ursprüngliche Liste. Wenn es sich nicht bereits in der Hashtabelle befindet, fügen Sie es zum Ergebnisarray hinzu und fügen Sie es der Hashtabelle hinzu. Wenn es in der Hash-Tabelle ist, ignorieren Sie es.

Dies ist bei weitem die beste Lösung. Also warum der Rest? Weil Probleme wie dieses darin bestehen, Wissen zu adaptieren, das Sie haben (oder haben sollten), zu Problemen und zu verfeinern, basierend auf den Annahmen, die Sie zu einer Lösung machen. Es ist viel nützlicher, eine Lösung zu entwickeln und das dahinterstehende Denken zu verstehen, als eine Lösung zu erbrechen.

Außerdem sind Hashtabellen nicht immer verfügbar. Nimm ein eingebettetes System oder etwas, wo der Platz SEHR begrenzt ist. Sie können eine schnelle Sortierung in einer Handvoll Opcodes implementieren, weit weniger als jede Hash-Tabelle.

Dies kann in amortisierten O (n) unter Verwendung einer Hashtable-basierten Menge erfolgen.

Pseudo-Code:

 s := new HashSet c := 0 for each el in a Add el to s. If el was not already in s, move (copy) el c positions left. If it was in s, increment c. 

Wenn Sie das ursprüngliche Objekt nicht beibehalten müssen, können Sie es schleifen und ein neues Array eindeutiger Werte erstellen. Verwenden Sie in C # eine Liste, um auf die erforderliche functionalität zuzugreifen. Es ist nicht die attraktivste oder intelligenteste Lösung, aber es funktioniert.

 int[] numbers = new int[] {1,2,3,4,5,1,2,2,2,3,4,5,5,5,5,4,3,2,3,4,5}; List unique = new List(); foreach (int i in numbers) if (!unique.Contains(i)) unique.Add(i); unique.Sort(); numbers = unique.ToArray(); 

Behandle Zahlen als Schlüssel.

 for each elem in array: if hash(elem) == 1 //duplicate ignore it next else hash(elem) = 1 add this to resulting array end 

Wenn Sie über die Daten wie den Bereich der Zahlen wissen und wenn es endlich ist, können Sie dieses große Array mit ZERO’s initialisieren.

 array flag[N] //N is the max number in the array for each elem in input array: if flag[elem - 1] == 0 flag[elem - 1] = 1 add it to resulatant array else discard it //duplicate end 

  indexOutput = 1; outputArray[0] = arrayInt[0]; int j; for (int i = 1; i < arrayInt.length; i++) { j = 0; while ((outputArray[j] != arrayInt[i]) && j < indexOutput) { j++; } if(j == indexOutput){ outputArray[indexOutput] = arrayInt[i]; indexOutput++; } } 

Verwenden Sie eine Set-Implementierung.
HashSet , TreeSet oder LinkedHashSet, wenn es Java ist.

Ich stimme Cletus zu. Verwenden Sie eine QuickSort und entfernen Sie dann die Duplikate

Dies ist ein Code-Segment, das ich in C ++ erstellt habe. Probieren Sie es aus

 #include  using namespace std; int main() { cout < < " Delete the duplicate" << endl; int numberOfLoop = 10; int loopCount =0; int indexOfLargeNumber = 0; int largeValue = 0; int indexOutput = 1; //Array to hold the numbers int arrayInt[10] = {}; int outputArray [10] = {}; // Loop for reading the numbers from the user input while(loopCount < numberOfLoop){ cout << "Please enter one Integer number" << endl; cin >> arrayInt[loopCount]; loopCount = loopCount + 1; } outputArray[0] = arrayInt[0]; int j; for (int i = 1; i < numberOfLoop; i++) { j = 0; while ((outputArray[j] != arrayInt[i]) && j < indexOutput) { j++; } if(j == indexOutput){ outputArray[indexOutput] = arrayInt[i]; indexOutput++; } } cout << "Printing the Non duplicate array"<< endl; //Reset the loop count loopCount =0; while(loopCount < numberOfLoop){ if(outputArray[loopCount] != 0){ cout << outputArray[loopCount] << endl; } loopCount = loopCount + 1; } return 0; } 

Meine Lösung ( O(N) ) verwendet keinen zusätzlichen Speicher, aber das Array muss sortiert sein (meine class verwendet den Insertion-Sort-Algorithmus, spielt aber keine Rolle):

  public class MyArray { //data arr private int[] _arr; //field length of my arr private int _leght; //counter of duplicate private int countOfDup = 0; //property length of my arr public int Length { get { return _leght; } } //constructor public MyArray(int n) { _arr = new int[n]; _leght = 0; } // put element into array public void Insert(int value) { _arr[_leght] = value; _leght++; } //Display array public void Display() { for (int i = 0; i < _leght; i++) Console.Out.Write(_arr[i] + " "); } //Insertion sort for sorting array public void InsertSort() { int t, j; for (int i = 1; i < _leght; i++) { t = _arr[i]; for (j = i; j > 0; ) { if (_arr[j - 1] >= t) { _arr[j] = _arr[j - 1]; j--; } else break; } _arr[j] = t; } } private void _markDuplicate() { //mark duplicate Int32.MinValue for (int i = 0; i < _leght - 1; i++) { if (_arr[i] == _arr[i + 1]) { countOfDup++; _arr[i] = Int32.MinValue; } } } //remove duplicates O(N) ~ O(2N) ~ O(N + N) public void RemoveDups() { _markDuplicate(); if (countOfDup == 0) return; //no duplicate int temp = 0; for (int i = 0; i < _leght; i++) { // if duplicate remember and continue if (_arr[i] == Int32.MinValue) continue; else //else need move { if (temp != i) _arr[temp] = _arr[i]; temp++; } } _leght -= countOfDup; } } 

Und Hauptsache

 static void Main(string[] args) { Random r = new Random(DateTime.Now.Millisecond); int i = 11; MyArray a = new MyArray(i); for (int j = 0; j < i; j++) { a.Insert(r.Next(i - 1)); } a.Display(); Console.Out.WriteLine(); a.InsertSort(); a.Display(); Console.Out.WriteLine(); a.RemoveDups(); a.Display(); Console.ReadKey(); } 
 import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Set; public class testing { public static void main(String[] args) { EligibleOffer efg = new EligibleOffer(); efg.setCode("1234"); efg.setName("hey"); EligibleOffer efg1 = new EligibleOffer(); efg1.setCode("1234"); efg1.setName("hey1"); EligibleOffer efg2 = new EligibleOffer(); efg2.setCode("1235"); efg2.setName("hey"); EligibleOffer efg3 = new EligibleOffer(); efg3.setCode("1235"); efg3.setName("hey"); EligibleOffer[] eligibleOffer = { efg, efg1,efg2 ,efg3}; removeDupliacte(eligibleOffer); } public static EligibleOffer[] removeDupliacte(EligibleOffer[] array) { List list = Arrays.asList(array); List list1 = new ArrayList(); int len = list.size(); for (int i = 0; i < = len-1; i++) { boolean isDupliacte = false; EligibleOffer eOfr = (EligibleOffer) list.get(i); String value = eOfr.getCode().concat(eOfr.getName()); if (list1.isEmpty()) { list1.add(list.get(i)); continue; } int len1 = list1.size(); for (int j = 0; j <= len1-1; j++) { EligibleOffer eOfr1 = (EligibleOffer) list1.get(j); String value1 = eOfr1.getCode().concat(eOfr1.getName()); if (value.equals(value1)) { isDupliacte = true; break; } System.out.println(value+"\t"+value1); } if (!isDupliacte) { list1.add(eOfr); } } System.out.println(list1); EligibleOffer[] eligibleOffer = new EligibleOffer[list1.size()]; list1.toArray(eligibleOffer); return eligibleOffer; } } 
 Time O(n) space O(n) #include  #include using namespace std; void fun(int arr[],int size){ int count=0; int has[100]={0}; for(int i=0;i 
 public class RemoveDuplicateArray { public static void main(String[] args) { int arr[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 2, 3, 4, 9 }; int size = arr.length; for (int i = 0; i < size; i++) { for (int j = i+1; j < size; j++) { if (arr[i] == arr[j]) { while (j < (size) - 1) { arr[j] = arr[j + 1]; j++; } size--; } } } for (int i = 0; i < size; i++) { System.out.print(arr[i] + " "); } } } 

Ausgabe - 1 2 3 4 5 6 7 9

Sie können die Syntax “in” und “nicht in” in Python verwenden, was es ziemlich einfach macht.

Die Komplexität ist jedoch höher als die Hashing-Methode, da ein “nicht in” einem linearen Durchlauf entspricht, um herauszufinden, ob dieser Eintrag existiert oder nicht.

 li = map(int, raw_input().split(",")) a = [] for i in li: if i not in a: a.append(i) print a