Вопрос о домашней работе массива

Вопрос немного двусмысленный; когда запрос «какой», означает ли это возврат дублируемого значения или позиции в последовательности дублированного? В первом случае подойдет любое из следующих трех решений; если второе, то поможет только первое.

Решение №1: предполагает, что массив неизменяемый

Построить растровое изображение; установите n -й бит при итерации по массиву. Если бит уже установлен, вы нашли дубликат. Он работает с линейным временем и будет работать с массивом любого размера.

Растровое изображение будет создано с таким количеством битов, сколько возможных значений в массиве. Во время итерации по массиву вы проверяете n -й бит в массиве. Если он установлен, вы нашли свой дубликат. Если это не так, установите его. (Логику для этого можно увидеть в псевдокоде этой статьи в Википедии о Битовых массивах или использовать класс System.Collections.BitArray .)

Решение №2: предполагает, что массив является изменяемым

Отсортируйте массив, а затем выполните линейный поиск, пока текущее значение не станет равным предыдущему значению. Использует меньше всего памяти.

Подсказка: используйте свойство, которое A XOR A == 0 и 0 XOR A == A.

Этот код 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 не пуст после удаления из него большего и меньшего , то должен быть дубликат, и он должен быть стержнем .

Код страдает от обычных проблем с переполнением стека для отсортированных данных, поэтому необходимо либо случайный поворот, либо итеративное решение, которое ставит данные в очередь:

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

Если предположить, что все числа от 1 до 1 000 000 находятся в массиве , сумма всех чисел от 1 до 1 000 000 будет (1,000,000) * (1,000,000 + 1) / 2 = 500 000 * 1 000 001 = 500 000 500 000 .

Так что просто сложите все числа в массиве, вычтите 500 000 500 000, и вы получите число, которое встречается дважды.

O (n) раз, и O (1) память.

Если предположение неверно , вы можете попробовать использовать фильтр Блума - они могут храниться намного компактнее, чем хэш-таблица (поскольку они хранят только факт присутствия), но они рискуют получить ложные срабатывания. Однако этот риск может быть ограничен нашим выбором того, сколько памяти потратить на фильтр Блума.

А как насчет проблемы поиска ВСЕХ дубликатов? Это можно сделать менее чем за O (n ln n) время? (Сортировка и сканирование) (Если вы хотите восстановить исходный массив, сохраните исходный индекс и измените порядок после конца, что можно сделать за O (n) раз)

В качестве варианта решения (2) вы можете использовать radix sort . Никакой дополнительной памяти, и будет работать линейное время. Вы можете утверждать, что время также зависит от размера представления чисел, но вы уже дали для этого границы: радиальная сортировка выполняется за время O (kn), где k - количество цифр, которое вы можете сортировать на каждом проходе. Это делает весь алгоритм O (7n) для сортировки плюс O (n) для проверки дублированного числа - что составляет O (8n) = O (n).

Плюсы:

• Нет дополнительной памяти
• O (n)

Минусы:

• Требуется восемь проходов O (n).

def singleton(array):
  return reduce(lambda x,y:x^y, array)

Вместо сортировки массива и последующей проверки я бы предложил написать реализацию функции сортировки сравнения, которая завершает как только будет найден дубликат, что приведет к отсутствию дополнительных требований к памяти (очевидно, в зависимости от выбранного вами алгоритма) и времени O (nlogn) в худшем случае (опять же, в зависимости от алгоритма), а не к лучшему (и среднему в зависимости ...) case O (nlogn) time.

Например, реализация сортировки слиянием на месте.

http://en.wikipedia.org/wiki/Merge_sort

Сортировка целых чисел путем сортировки их по месту, где они должны быть. Если вы получили "коллизию", значит, вы нашли правильный номер.

сложность пространства O (1) (точно такое же пространство, которое можно перезаписать) временная сложность меньше, чем O (n), потому что вы статистически обнаружите столкновение, прежде чем попадете в конец.