Ce code python est une modification de QuickSort:
def findDuplicate(arr):
orig_len = len(arr)
if orig_len <= 1:
return None
pivot = arr.pop(0)
greater = [i for i in arr if i > pivot]
lesser = [i for i in arr if i < pivot]
if len(greater) + len(lesser) != orig_len - 1:
return pivot
else:
return findDuplicate(lesser) or findDuplicate(greater)
Il trouve un doublon en O(n logn)), je pense. Il utilise de la mémoire supplémentaire sur la pile, mais il peut être réécrit pour utiliser une seule copie des données d'origine, je crois:
def findDuplicate(arr):
orig_len = len(arr)
if orig_len <= 1:
return None
pivot = arr.pop(0)
greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot]
lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot]
if len(arr):
return pivot
else:
return findDuplicate(lesser) or findDuplicate(greater)
Les interprétations de la liste que produire plus et à moindre détruire l'original avec des appels à la pop(). Si arr n'est pas vide après la suppression de plus et de moins , alors il doit y avoir un doublon et il doit être pivot.
Le code souffre de l'habitude de débordement de pile problèmes sur les données triées, donc, soit de façon aléatoire un pivot ou une solution itérative qui les files d'attente de données est nécessaire:
def findDuplicate(full):
import copy
q = [full]
while len(q):
arr = copy.copy(q.pop(0))
orig_len = len(arr)
if orig_len > 1:
pivot = arr.pop(0)
greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot]
lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot]
if len(arr):
return pivot
else:
q.append(greater)
q.append(lesser)
return None
Cependant, maintenant que le code doit prendre une profonde copie des données dans le haut de la boucle, la modification de la mémoire.
Autant pour l'informatique. Les naïfs algorithme clobbers mon code en python, probablement en raison de python algorithme de tri:
def findDuplicate(arr):
arr = sorted(arr)
prev = arr.pop(0)
for element in arr:
if element == prev:
return prev
else:
prev = element
return None
