Этот код Python является модификацией 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)
Он находит дубликат в O (n logn)), я думаю. Он использует дополнительную память в стеке, но его можно переписать, чтобы использовать только одну копию исходных данных, я считаю:
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)
Понимания списка, которые производят больше и меньше уничтожают оригинал с помощью вызовов pop (). Если arr не является пустым после удаления больше и меньше , то должен быть дубликат, и он должен быть pivot .
Код страдает от обычных проблем переполнения стека отсортированных данных, поэтому требуется либо случайный свод, либо итеративное решение, которое ставит в очередь данные:
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
Однако теперь код должен делать глубокую копию данных в верхней части цикла, изменяя требования к памяти.
Так много для информатики. Наивный алгоритм забивает мой код на python, возможно, из-за алгоритма сортировки python:
def findDuplicate(arr):
arr = sorted(arr)
prev = arr.pop(0)
for element in arr:
if element == prev:
return prev
else:
prev = element
return None