Finde Duplikate in einem Array / einer Liste von Ganzzahlen - Python, Arrays, Algorithmus, Liste, Sortierung

Gegeben ein array/list von integersgeben die Duplikate aus.

Und was ich wirklich suche: Welche Lösungen haben die beste Zeitleistung? Beste Platzleistung? Ist es möglich, sowohl die beste Zeit als auch die beste Raumleistung zu erzielen? Nur neugierig. Vielen Dank!

Zum Beispiel: die Liste gegeben [4,1,7,9,4,5,2,7,6,5,3,6,7]wäre die Antwort [4,7,6,5] (Die Reihenfolge der Ausgabe spielt keine Rolle).

Ich habe meine Lösung in geschrieben python.

Hier ist eine Lösung, die ich mit einem Hash und einer binären Suche geschrieben habe.

def binarySearch(array, number):
start = 0
end = len(array)
mid = (end + start) // 2
while (end > start):
mid = start + (end - start) // 2
if array[mid] == number:
return (mid, True)
elif number > array[mid]:
if start == mid:
return (mid + 1, False)
start = mid
else:
end = mid

return (mid, False)

def findDuplicatesWithHash(array):
duplicatesHash = {}
duplicates = []
for number in array:
try:
index,found = binarySearch(duplicates, number)
if duplicatesHash[number] == 0 and not found:
duplicates.insert(index, number)
except KeyError as error:
duplicatesHash[number] = 0

duplicatesSorted = sorted(duplicates, key=lambda tup: tup)
return duplicatesSorted

Antworten:

Eine Möglichkeit, das Duplikat zu erhalten:

l = [4,1,7,9,4,5,2,7,6,5,3,6]
import collections

print([item for item, count in collections.Counter(l).items() if count > 1])

Das Finden von Duplikaten ist dem Sortieren sehr ähnlich. Das heißt, jedes Element muss direkt oder indirekt mit allen anderen Elementen verglichen werden, um festzustellen, ob Duplikate vorhanden sind. Man könnte Quicksort so ändern, dass Elemente ausgegeben werden, die ein benachbartes Übereinstimmungselement mit O (n) räumlicher Komplexität und O (n * log (n)) Durchschnittszeitkomplexität aufweisen.

Es gibt mehrere Lösungen, um Duplikate zu finden. Da diese Frage völlig generisch ist, kann man davon ausgehen, dass eine Liste von n Werte liegt die Anzahl der Duplikate im Bereich [0, n/2].

Was sind die möglichen Methoden, die Sie sich vorstellen können?

1. Hash Table Ansatz:

   Speichern Sie Werte beim Durchlaufen der Liste, wenn der Wert nicht bereits in der Hashtabelle vorhanden ist. Wenn der Wert vorhanden ist, haben Sie ein Duplikat.

   Algorithm FindDuplicates(list)
   hash_table <- HashTable()
   duplicates <- List()
   for value in list:
   if value in hash_table:
   duplicates.add(value)
   else:
   hash_table.add(value, true)
   

   • Zeit: O(n) alle Werte durchqueren
   • Platz: O(n) um alle möglichen Werte in der Hashtabelle zu speichern.

2. Array sortieren

   Sortieren Sie das Array und durchqueren Sie die Nachbarwerte.

   Algorithm FindDuplicates(list)
   list.sort()
   duplicates <- Set()
   for i <- [1, len(list)-1]:
   if list[i] = list[i-1]:
   duplicates.add(list[i])
   

   • Zeit: O(n.logn) + O(n) = O(n.logn) alle Werte sortieren und durchqueren
   • Platz: O(1) da kein zusätzlicher Platz geschaffen wurde, um Duplikate zu erzeugen

3. Überprüfen Sie für jeden Wert

   Prüfen Sie für jeden Wert, ob der Wert im Array vorhanden ist.

   Algorithm Search(i, list):
   for j <- [0, len(list)-1] - [i]:
   if list[j] = list[i]:
   return true
   return false
   
   Algorithm FindDuplicates(list)
   duplicates <- Set()
   for i <- [1, len(list)-1]:
   if Search(i, list):
   duplicates.add(list[i])
   

   Zeit: O(n^2) Anzahl der Vergleiche sind n*n(-1) Platz: O(1) da kein zusätzlicher Platz geschaffen wurde, um Duplikate zu erzeugen

Hinweis: Der Platz für das Duplikat-Array kann nicht in die Komplexitätsgleichungen für den Raum eingeschlossen werden.

Fällt Ihnen noch etwas ein?